Stochastic makespan minimization in structured set systems

• Published in: Mathematical programming 2022-03, Vol.192 (1-2), p.597-630
• Main Authors: Gupta, Anupam, Kumar, Amit, Nagarajan, Viswanath, Shen, Xiangkun
• Format: Article
• Language: English
• 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
• ISSN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-021-01741-z

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.