Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract)

Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings
EditorsDaniel Bienstock, Giacomo Zambelli
PublisherSpringer
Pages158-170
Number of pages13
ISBN (Print)9783030457709
DOIs
StatePublished - 2020
Event21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 - London, United Kingdom
Duration: Jun 8 2020Jun 10 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
Country/TerritoryUnited Kingdom
CityLondon
Period6/8/206/10/20

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract)'. Together they form a unique fingerprint.

Cite this