TY - JOUR

T1 - Stochastic makespan minimization in structured set systems

AU - Gupta, Anupam

AU - Kumar, Amit

AU - Nagarajan, Viswanath

AU - Shen, Xiangkun

N1 - Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2022/3

Y1 - 2022/3

N2 - 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 Xj, 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.

AB - 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 Xj, 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.

KW - Approximation algorithms

KW - Geometric packing

KW - Linear programming

KW - Stochastic optimization

UR - http://www.scopus.com/inward/record.url?scp=85120006432&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85120006432&partnerID=8YFLogxK

U2 - 10.1007/s10107-021-01741-z

DO - 10.1007/s10107-021-01741-z

M3 - Article

AN - SCOPUS:85120006432

SN - 0025-5610

VL - 192

SP - 597

EP - 630

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -