Stochastic makespan minimization in structured set systems

• 成果类型: Article
• 署名作者: Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
• 署名单位: Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan; Yahoo! Inc
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01741-z
• 发表日期: 2022
• 页码: 597-630
• 关键词: approximation algorithms; independent set; bandwidth; objects; UNION

摘要

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 Omega(log* m) integrality gap, even for the problem of selecting intervals on a line; here log* m is the iterated logarithm function.