Stochastic makespan minimization in structured set systems

Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)597-630
Number of pages34
JournalMathematical Programming
Issue number1-2
StatePublished - Mar 2022


  • Approximation algorithms
  • Geometric packing
  • Linear programming
  • Stochastic optimization

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Stochastic makespan minimization in structured set systems'. Together they form a unique fingerprint.

Cite this