About the Structure of the Integer Cone and Its Application to Bin Packing

• 成果类型: Article
• 署名作者: Jansen, Klaus; Klein, Kim-Manuel
• 署名单位: University of Kiel
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.1040
• 发表日期: 2020
• 页码: 1498-1511
• 关键词: points; number

摘要

We consider the bin packing problem with d different item sizes and revisit the structure theorem given by Goemans and Rothvoss 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 vertical bar V vertical bar 2(O(d)) center dot enc(I)(O(1)), where V is the set of vertices of the integer knapsack polytope, and enc(I) is 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 vertical bar V vertical bar. 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.