A Quasi-Polynomial Approximation for the Restricted Assignment Problem
A Quasi-Polynomial Approximation for the Restricted Assignment Problem
复制标题
DOI：
10.1007/978-3-319-59250-3_25
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
K. Jansen;Lars Rohwedder
中科院分区：
文献类型：
--
作者：
K. Jansen;Lars Rohwedder
在不相关的机器上安排作业并最小化完工时间是组合优化中的一个经典问题。一项工作每台机器都有一个处理时间。针对此问题已知的最佳多项式算法可以追溯到 Lenstra 等人。并且近似比率为 2。在本文中，我们研究了限制分配问题，这是其中的特殊情况。我们针对这个问题提出了一种算法，其近似比率为 ，并且每个算法的运行时间为拟多项式。这缩小了与已知的拟多项式运行时间问题的最佳估计算法的差距。
Scheduling jobs on unrelated machines and minimizing the makespan is a classical problem in combinatorial optimization. A jobjhas a processing timefor every machinei. The best polynomial algorithm known for this problem goes back to Lenstra et al. and has an approximation ratio of 2. In this paper we study theRestricted Assignmentproblem, which is the special case where. We present an algorithm for this problem with an approximation ratio ofand quasi-polynomial running timefor every. This closes the gap to the best estimation algorithm known for the problem with regard to quasi-polynomial running time.