Santa Claus schedules jobs on unrelated machines
Santa Claus schedules jobs on unrelated machines
复制标题
DOI：
10.1145/1993636.1993718
复制
发表时间：
2010-11
期刊：
影响因子：
--
通讯作者：
O. Svensson
中科院分区：
文献类型：
--
作者：
O. Svensson
排序理论中的经典结果之一是Lenstra，Shmoys和Tardos的2-近似算法，用于排序工件以最小化不相关机器上的完工时间的问题，即，如果在机器i上处理，作业j需要时间pij。在其引入后的二十多年里，它仍然是选择的算法，即使在处理时间为pij ∈ pj，∞的形式的限制模型中。这个问题，也被称为限制分配问题，是NP-难的近似在一个因子小于1.5，这也是最有名的下限的一般版本。我们的主要结果是一个多项式时间算法，估计的最优完工时间的限制性分配问题的一个因素33/17 + ε ~ 1.9412 + ε，其中ε > 0是一个任意小的常数。结果是通过上界的完整性差距的某一强线性规划，称为配置LP，这是以前成功地用于相关的圣诞老人问题。类似于对该问题的最强分析，我们的证明基于局部搜索算法，该算法最终将找到上述近似保证的时间表，但不知道在多项式时间内收敛。
One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time pij if processed on machine i. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form pij ∈ pj, ∞. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5 which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 33/17 + ε ~ 1.9412 + ε, where ε > 0 is an arbitrarily small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee, but is not known to converge in polynomial time.