2022/03/18 by Alexandra Lassota, Lassota, Alexandra, Aleksander Łukasiewicz +3
Engineering · Computer Science · #Optimization and Packing Problems #Advanced Manufacturing and Logistics Optimization #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2203.10077
We solve the Bin Packing problem in O^*(2k) time, where k is the number\nof items less or equal to one third of the bin capacity. This parameter\nmeasures the distance from the polynomially solvable case of only large (i.e.,\ngreater than one third) items. Our algorithm is actually designed to work for a\nmore general Vector Bin Packing problem, in which items are multidimensional\nvectors. We improve over the previous fastest O^*(k! \⋅ 4k) time\nalgorithm.\n Our algorithm works by reducing the problem to finding an exact weight\nperfect matching in a (multi-)graph with O^*(2k) edges, whose weights are\nintegers of the order of O^*(2k). To solve the matching problem in the\ndesired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani\nalgorithm with only a linear dependence on the edge weights and the number of\nedges, which may be of independent interest.\n Moreover, we give a tight lower bound, under the Strong Exponential Time\nHypothesis (SETH), showing that the constant 2 in the base of the exponent\ncannot be further improved for Vector Bin Packing.\n Our techniques also lead to improved algorithms for Vector Multiple Knapsack,\nVector Bin Covering, and Perfect Matching with Hitting Constraints.\n