TY - GEN

T1 - Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract)

AU - Gupta, Anupam

AU - Kumar, Amit

AU - Nagarajan, Viswanath

AU - Shen, Xiangkun

N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2020

Y1 - 2020

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, given a set of intervals in time, with each interval j having random load Xj, how do we choose t intervals to minimize the expected maximum load at any time? 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. Specifically, we give an O(log logm)-approximation algorithm for all these problems. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show an LP integrality gap of Ω(log*m) even for the problem of selecting intervals on a line.

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, given a set of intervals in time, with each interval j having random load Xj, how do we choose t intervals to minimize the expected maximum load at any time? 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. Specifically, we give an O(log logm)-approximation algorithm for all these problems. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show an LP integrality gap of Ω(log*m) even for the problem of selecting intervals on a line.

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

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

U2 - 10.1007/978-3-030-45771-6_13

DO - 10.1007/978-3-030-45771-6_13

M3 - Conference contribution

AN - SCOPUS:85083971027

SN - 9783030457709

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 170

BT - Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings

A2 - Bienstock, Daniel

A2 - Zambelli, Giacomo

PB - Springer

T2 - 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020

Y2 - 8 June 2020 through 10 June 2020

ER -