论文标题
在结构化设置系统中的随机制造pan最小化
Stochastic Makespan Minimization in Structured Set Systems
论文作者
论文摘要
我们研究随机组合优化问题，目的是最大程度地减少预期的最大载荷（又称Makepan）。在此框架中，我们有一组$ n $的任务和$ m $资源，其中每个任务$ j $都使用了某些资源。任务具有随机尺寸$ x_j $，我们的目标是非自动选择$ t $任务，以最大程度地减少所有资源的预期最大负载，其中任何资源$ i $上的负载是使用$ i $的所有选定任务的总尺寸。例如，当资源是点和任务是行中的间隔时，我们将获得$ O（\ log \ log M）$ - 近似算法。我们的技术还适用于任务和资源之间关系中一些几何结构的其他问题；例如，包装路径，矩形和“脂肪”对象。我们的方法使用随机变量的累积生成函数使用强大的LP松弛。我们还表明，即使是在行上选择间隔的问题，该LP具有$ω（\ log^* m）$的完整性差距。这里$ \ log^* m $是迭代对数函数。
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.
