About the Structure of the Integer Cone and its Application to Bin Packing
About the Structure of the Integer Cone and its Application to Bin Packing
复制标题
整数锥体的结构及其在装箱中的应用
DOI：
10.1137/1.9781611974782.103
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Klein
中科院分区：
文献类型：
--
作者：
K. Jansen;K. Klein
本文考虑了具有不同项目大小的装箱问题，并重新讨论了Goemans和Rothvovich给出的关于整数锥解的结构定理。我们提出了新的技术，解决方案可以被修改，并给出了一个新的结构定理，依赖于一组顶点的基础整数多面体。作为新结构定理的结果，我们得到了一个带运行时间的装箱问题的算法，其中V是整数背包多面体的顶点集，V是装箱实例的编码长度。该算法是固定参数易处理的，参数的整数背包多面体的顶点数。这表明，当底层整数背包多面体具有简单的结构（即，具有少量顶点）。此外，我们证明了结构定理的界是渐近紧的。我们给出了一个建设装箱的情况下，使用新的结构的见解和经典的数论定理，产生所需的下限。
We consider the bin packing problem withddifferent item sizes and revisit the structure theorem given by Goemans and Rothvoß about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time, whereVis the set of vertices of the integer knapsack polytope, andis the encoding length of the bin packing instance. The algorithm is fixed-parameter tractable, parameterized by the number of vertices of the integer knapsack polytope. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure (i.e., has a small number of vertices). Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound.