2016/04/25 by Klaus Jansen, Jansen, Klaus, Kim-Manuel Klein +1 · 2 citations
Engineering · #Optimization and Packing Problems #Advanced Manufacturing and Logistics Optimization #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1604.07286
We consider the bin packing problem with d different item sizes and revisit\nthe structure theorem given by Goemans and Rothvo ss [6] about solutions of the\ninteger cone. We present new techniques on how solutions can be modified and\ngive a new structure theorem that relies on the set of vertices of the\nunderlying integer polytope. As a result of our new structure theorem, we\nobtain an algorithm for the bin packing problem with running time\n|V|^2O(d) \⋅ enc(I)O(1), where V is the set of vertices of the\ninteger knapsack polytope and enc(I) is the encoding length of the bin\npacking instance. The algorithm is fixed parameter tractable, parameterized by\nthe number of vertices of the integer knapsack polytope |V|. This shows that\nthe bin packing problem can be solved efficiently when the underlying integer\nknapsack polytope has an easy structure, i.e. has a small number of vertices.\n Furthermore, we show that the presented bounds of the structure theorem are\nasymptotically tight. We give a construction of bin packing instances using new\nstructural insights and classical number theoretical theorems which yield the\ndesired lower bound.\n