Loading…
Stochastic makespan minimization in structured set systems
We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X j , and our goal is...
Saved in:
| Published in: | Mathematical programming 2022-03, Vol.192 (1-2), p.597-630 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | |
|---|---|
| cites | cdi_FETCH-LOGICAL-c309t-69626d35b1beed87735ca3547b28ac1d9f4d05413b7691ee8a8d7f033537ff323 |
| container_end_page | 630 |
| container_issue | 1-2 |
| container_start_page | 597 |
| container_title | Mathematical programming |
| container_volume | 192 |
| creator | Gupta, Anupam Kumar, Amit Nagarajan, Viswanath Shen, Xiangkun |
| description | We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of
n
tasks and
m
resources, where each task
j
uses some subset of the resources. Tasks have random sizes
X
j
, and our goal is to non-adaptively select
t
tasks to minimize the expected maximum load over all resources, where the load on any resource
i
is the total size of all selected tasks that use
i
. For example, when resources are points and tasks are intervals in a line, we obtain an
O
(
log
log
m
)
-approximation algorithm. Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and “fat” objects. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an
Ω
(
log
∗
m
)
integrality gap, even for the problem of selecting intervals on a line; here
log
∗
m
is the iterated logarithm function. |
| doi_str_mv | 10.1007/s10107-021-01741-z |
| format | article |
| fullrecord | <record><control><sourceid>gale_proqu</sourceid><recordid>TN_cdi_proquest_journals_2637650309</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A703948658</galeid><sourcerecordid>A703948658</sourcerecordid><originalsourceid>FETCH-LOGICAL-c309t-69626d35b1beed87735ca3547b28ac1d9f4d05413b7691ee8a8d7f033537ff323</originalsourceid><addsrcrecordid>eNp9kE1LxDAQhoMouK7-AU8Fz1knTZO03pbFLxA8qOeQpsmadZuuSXrY_fVGK3iTOQwM7zMzPAhdElgQAHEdCRAQGEqCgYiK4MMRmpGKclzxih-jGUDJMOMETtFZjBsAILSuZ-jmJQ36XcXkdNGrDxN3yhe98653B5Xc4Avni5jCqNMYTFdEk4q4j8n08RydWLWN5uK3z9Hb3e3r6gE_Pd8_rpZPWFNoEuYNL3lHWUtaY7paCMq0oqwSbVkrTbrGVh2witBW8IYYU6u6ExYoZVRYS0s6R1fT3l0YPkcTk9wMY_D5pCw5FZxBvpNTiym1VlsjnbdDCkrn6kzv9OCNdXm-FECbquaszkA5AToMMQZj5S64XoW9JCC_pcpJqsxS5Y9UecgQnaCYw35twt8v_1BfPz15yQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2637650309</pqid></control><display><type>article</type><title>Stochastic makespan minimization in structured set systems</title><source>Business Source Ultimate</source><source>Springer Nature</source><creator>Gupta, Anupam ; Kumar, Amit ; Nagarajan, Viswanath ; Shen, Xiangkun</creator><creatorcontrib>Gupta, Anupam ; Kumar, Amit ; Nagarajan, Viswanath ; Shen, Xiangkun</creatorcontrib><description>We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of
n
tasks and
m
resources, where each task
j
uses some subset of the resources. Tasks have random sizes
X
j
, and our goal is to non-adaptively select
t
tasks to minimize the expected maximum load over all resources, where the load on any resource
i
is the total size of all selected tasks that use
i
. For example, when resources are points and tasks are intervals in a line, we obtain an
O
(
log
log
m
)
-approximation algorithm. Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and “fat” objects. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an
Ω
(
log
∗
m
)
integrality gap, even for the problem of selecting intervals on a line; here
log
∗
m
is the iterated logarithm function.</description><identifier>ISSN: 0025-5610</identifier><identifier>EISSN: 1436-4646</identifier><identifier>DOI: 10.1007/s10107-021-01741-z</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Algorithms ; Calculus of Variations and Optimal Control; Optimization ; Combinatorial analysis ; Combinatorics ; Full Length Paper ; Intervals ; Mathematical analysis ; Mathematical and Computational Physics ; Mathematical Methods in Physics ; Mathematics ; Mathematics and Statistics ; Mathematics of Computing ; Numerical Analysis ; Optimization ; Random variables ; Rectangles ; Theoretical</subject><ispartof>Mathematical programming, 2022-03, Vol.192 (1-2), p.597-630</ispartof><rights>Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2021</rights><rights>COPYRIGHT 2022 Springer</rights><rights>Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2021.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c309t-69626d35b1beed87735ca3547b28ac1d9f4d05413b7691ee8a8d7f033537ff323</cites><orcidid>0000-0002-9514-5581</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,778,782,27907,27908</link.rule.ids></links><search><creatorcontrib>Gupta, Anupam</creatorcontrib><creatorcontrib>Kumar, Amit</creatorcontrib><creatorcontrib>Nagarajan, Viswanath</creatorcontrib><creatorcontrib>Shen, Xiangkun</creatorcontrib><title>Stochastic makespan minimization in structured set systems</title><title>Mathematical programming</title><addtitle>Math. Program</addtitle><description>We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of
n
tasks and
m
resources, where each task
j
uses some subset of the resources. Tasks have random sizes
X
j
, and our goal is to non-adaptively select
t
tasks to minimize the expected maximum load over all resources, where the load on any resource
i
is the total size of all selected tasks that use
i
. For example, when resources are points and tasks are intervals in a line, we obtain an
O
(
log
log
m
)
-approximation algorithm. Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and “fat” objects. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an
Ω
(
log
∗
m
)
integrality gap, even for the problem of selecting intervals on a line; here
log
∗
m
is the iterated logarithm function.</description><subject>Algorithms</subject><subject>Calculus of Variations and Optimal Control; Optimization</subject><subject>Combinatorial analysis</subject><subject>Combinatorics</subject><subject>Full Length Paper</subject><subject>Intervals</subject><subject>Mathematical analysis</subject><subject>Mathematical and Computational Physics</subject><subject>Mathematical Methods in Physics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Mathematics of Computing</subject><subject>Numerical Analysis</subject><subject>Optimization</subject><subject>Random variables</subject><subject>Rectangles</subject><subject>Theoretical</subject><issn>0025-5610</issn><issn>1436-4646</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAQhoMouK7-AU8Fz1knTZO03pbFLxA8qOeQpsmadZuuSXrY_fVGK3iTOQwM7zMzPAhdElgQAHEdCRAQGEqCgYiK4MMRmpGKclzxih-jGUDJMOMETtFZjBsAILSuZ-jmJQ36XcXkdNGrDxN3yhe98653B5Xc4Avni5jCqNMYTFdEk4q4j8n08RydWLWN5uK3z9Hb3e3r6gE_Pd8_rpZPWFNoEuYNL3lHWUtaY7paCMq0oqwSbVkrTbrGVh2witBW8IYYU6u6ExYoZVRYS0s6R1fT3l0YPkcTk9wMY_D5pCw5FZxBvpNTiym1VlsjnbdDCkrn6kzv9OCNdXm-FECbquaszkA5AToMMQZj5S64XoW9JCC_pcpJqsxS5Y9UecgQnaCYw35twt8v_1BfPz15yQ</recordid><startdate>20220301</startdate><enddate>20220301</enddate><creator>Gupta, Anupam</creator><creator>Kumar, Amit</creator><creator>Nagarajan, Viswanath</creator><creator>Shen, Xiangkun</creator><general>Springer Berlin Heidelberg</general><general>Springer</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0002-9514-5581</orcidid></search><sort><creationdate>20220301</creationdate><title>Stochastic makespan minimization in structured set systems</title><author>Gupta, Anupam ; Kumar, Amit ; Nagarajan, Viswanath ; Shen, Xiangkun</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c309t-69626d35b1beed87735ca3547b28ac1d9f4d05413b7691ee8a8d7f033537ff323</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Calculus of Variations and Optimal Control; Optimization</topic><topic>Combinatorial analysis</topic><topic>Combinatorics</topic><topic>Full Length Paper</topic><topic>Intervals</topic><topic>Mathematical analysis</topic><topic>Mathematical and Computational Physics</topic><topic>Mathematical Methods in Physics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Mathematics of Computing</topic><topic>Numerical Analysis</topic><topic>Optimization</topic><topic>Random variables</topic><topic>Rectangles</topic><topic>Theoretical</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Gupta, Anupam</creatorcontrib><creatorcontrib>Kumar, Amit</creatorcontrib><creatorcontrib>Nagarajan, Viswanath</creatorcontrib><creatorcontrib>Shen, Xiangkun</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Mathematical programming</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gupta, Anupam</au><au>Kumar, Amit</au><au>Nagarajan, Viswanath</au><au>Shen, Xiangkun</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Stochastic makespan minimization in structured set systems</atitle><jtitle>Mathematical programming</jtitle><stitle>Math. Program</stitle><date>2022-03-01</date><risdate>2022</risdate><volume>192</volume><issue>1-2</issue><spage>597</spage><epage>630</epage><pages>597-630</pages><issn>0025-5610</issn><eissn>1436-4646</eissn><abstract>We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of
n
tasks and
m
resources, where each task
j
uses some subset of the resources. Tasks have random sizes
X
j
, and our goal is to non-adaptively select
t
tasks to minimize the expected maximum load over all resources, where the load on any resource
i
is the total size of all selected tasks that use
i
. For example, when resources are points and tasks are intervals in a line, we obtain an
O
(
log
log
m
)
-approximation algorithm. Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and “fat” objects. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an
Ω
(
log
∗
m
)
integrality gap, even for the problem of selecting intervals on a line; here
log
∗
m
is the iterated logarithm function.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s10107-021-01741-z</doi><tpages>34</tpages><orcidid>https://orcid.org/0000-0002-9514-5581</orcidid></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0025-5610 |
| ispartof | Mathematical programming, 2022-03, Vol.192 (1-2), p.597-630 |
| issn | 0025-5610 1436-4646 |
| language | eng |
| recordid | cdi_proquest_journals_2637650309 |
| source | Business Source Ultimate; Springer Nature |
| subjects | Algorithms Calculus of Variations and Optimal Control Optimization Combinatorial analysis Combinatorics Full Length Paper Intervals Mathematical analysis Mathematical and Computational Physics Mathematical Methods in Physics Mathematics Mathematics and Statistics Mathematics of Computing Numerical Analysis Optimization Random variables Rectangles Theoretical |
| title | Stochastic makespan minimization in structured set systems |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-16T05%3A01%3A02IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_proqu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Stochastic%20makespan%20minimization%20in%20structured%20set%20systems&rft.jtitle=Mathematical%20programming&rft.au=Gupta,%20Anupam&rft.date=2022-03-01&rft.volume=192&rft.issue=1-2&rft.spage=597&rft.epage=630&rft.pages=597-630&rft.issn=0025-5610&rft.eissn=1436-4646&rft_id=info:doi/10.1007/s10107-021-01741-z&rft_dat=%3Cgale_proqu%3EA703948658%3C/gale_proqu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c309t-69626d35b1beed87735ca3547b28ac1d9f4d05413b7691ee8a8d7f033537ff323%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2637650309&rft_id=info:pmid/&rft_galeid=A703948658&rfr_iscdi=true |