Stochastic makespan minimization in structured set systems
Stochastic makespan minimization in structured set systems
复制标题
结构化集合系统中的随机完工时间最小化
DOI：
10.1007/s10107-021-01741-z
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Shen, Xiangkun
中科院分区：
文献类型：
--
作者：
Gupta, Anupam;Kumar, Amit;Nagarajan, Viswanath;Shen, Xiangkun
我们研究随机组合优化问题，其中目标是最小化期望最大负荷(又名。工期)。在这个框架中，我们有一组任务和资源，其中每个任务占用资源的某个子集。任务的大小是随机的，我们的目标是非适应性地选择任务，以最小化所有资源上的预期最大负载，其中任何资源上的负载都是用户选择的所有任务的总大小。例如，当资源是点，任务是直线上的区间时，我们得到了一个近似算法。我们的技术也适用于任务和资源关系中具有某种几何结构的其他问题，例如打包路径、矩形和“胖”对象。我们的方法利用随机变量的累积量母函数来实现强Lp松弛。我们还证明了，即使对于直线上选择区间的问题，这个LP也有非完整性缺口；这里是重对数函数。
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 ofntasks andmresources, where each taskjuses some subset of the resources. Tasks have random sizes, and our goal is to non-adaptively selectttasks to minimize the expected maximum load over all resources, where the load on any resourceiis the total size of all selected tasks that usei. For example, when resources are points and tasks are intervals in a line, we obtain an-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 anintegrality gap, even for the problem of selecting intervals on a line; hereis the iterated logarithm function.
登录
查看更多内容
DOI：
10.1137/1.9781611976465.54
发表时间：
2020
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Parinya Chalermsook;Bartosz Walczak
通讯作者：
Bartosz Walczak
DOI：
10.1137/1.9781611973068.97
发表时间：
2009
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Parinya Chalermsook;Julia Chuzhoy
通讯作者：
Julia Chuzhoy
DOI：
10.1137/1.9781611975031.83
发表时间：
2018-01
期刊：
ArXiv
影响因子：
--
作者：
Anupam Gupta;Amit Kumar;V. Nagarajan;Xiangkun Shen
通讯作者：
Anupam Gupta;Amit Kumar;V. Nagarajan;Xiangkun Shen
改进了平面中局部胖对象联合的界限
DOI：
10.1137/120891241
发表时间：
2014
期刊：
SIAM J. Comput.
影响因子：
--
作者：
B. Aronov;M. D. Berg;Esther Ezra;M. Sharir
通讯作者：
M. Sharir
如何驯服矩形：通过收缩解决矩形的独立集和着色问题
DOI：
10.4230/lipics.approx-random.2015.43
发表时间：
2015
期刊：
IEEE International Conference on Communications, - Spanning the Universe.
影响因子：
--
作者：
Anna Adamaszek;Parinya Chalermsook;Andreas Wiese
通讯作者：
Andreas Wiese