Closing the Gap for Makespan Scheduling via Sparsification Techniques
Closing the Gap for Makespan Scheduling via Sparsification Techniques
复制标题
DOI：
10.4230/lipics.icalp.2016.72
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
K. Jansen;Kim-Manuel Klein;José Verschae
中科院分区：
文献类型：
--
作者：
K. Jansen;Kim-Manuel Klein;José Verschae
同类机器的最大完工时间排序问题是离散优化文献中研究的最基本的装箱问题之一。它要求将n个工件分配给一组m台相同的机器，使完工时间最小化。这个问题是强NP难的，因此我们不期望一个运行时间多项式依赖于[公式：见正文]的（[公式：见正文]）近似算法。最近已经表明，[公式：见正文]上的次指数运行时间意味着指数时间假设（ETH）失败。已经开发了一长串算法，试图获得对[公式：见正文]的低依赖性，其中较好的算法实现了对指数的二次运行时间。在本文中，我们得到了一个算法，该算法在指数中对[公式：见正文]具有几乎线性的依赖性，在ETH下直到对数因子都是紧的。我们的主要技术贡献是一个新的结构上的配置-IP整数线性规划的结果。更准确地说，我们证明了高度对称且稀疏的最佳解的存在，其中除了恒定数量的机器之外，所有机器都被分配了具有小支持的配置。然后可以通过整数编程技术和枚举来利用此结构。我们相信，我们的结构结果是独立的利益，并应找到其他设置的应用程序。我们通过将我们的结构结果应用于相关机器上的最小完工时间问题和并行机器上的更大类的目标函数来证明这一点。对于所有这些情况，我们获得了一个有效的PTAS，其运行时间几乎线性依赖于[公式：见正文]和n中的多项式。
Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of n jobs to a set of m identical machines that minimizes the makespan. The problem is strongly NP-hard, and thus we do not expect a ([Formula: see text])-approximation algorithm with a running time that depends polynomially on [Formula: see text]. It has been recently shown that a subexponential running time on [Formula: see text] would imply that the Exponential Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on [Formula: see text], the better of which achieves a quadratic running time on the exponent. In this paper we obtain an algorithm with an almost-linear dependency on [Formula: see text] in the exponent, which is tight under ETH up to logarithmic factors. Our main technical contribution is a new structural result on the configuration-IP integer linear program. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. We exemplify this by applying our structural results to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases, we obtain an efficient PTAS with running time with an almost-linear dependency on [Formula: see text] and polynomial in n.