论文标题
紧密的矢量箱包装包装有几个小物品，可以通过多绘画中的快速匹配
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
论文作者
论文摘要
我们以$ o^*（2^k）$时间解决了bin包装问题，其中$ k $是较小或等于垃圾箱容量的三分之一的物品的数量。该参数可测量仅大型（即大于三分之一）的多项式可求解情况的距离。我们的算法实际上是为了解决一个更通用的矢量箱包装问题，其中项目是多维矢量。我们比以前的最快$ o^*（k！\ cdot 4^k）$ time算法改进。 我们的算法通过减少问题来找到与$ o^*（2^k）$边缘的（多）图中的精确匹配的问题，其权重是$ o^*（2^k）$的整数。为了解决所需时间的匹配问题，我们给出了经典的Mulmuley-Vazirani-Vazirani算法的变体，只有线性依赖边缘重量和边缘的数量，这可能是独立的。 此外，在强大的指数时间假设（SETH）下，我们给出了一个紧密的下限，表明，对于矢量箱填料，无法进一步改善指数基础的恒定$ 2 $。 我们的技术还可以改善矢量多背包，矢量箱盖的算法，并与命中约束完美匹配。
We solve the Bin Packing problem in $O^*(2^k)$ time, where $k$ is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. Our algorithm is actually designed to work for a more general Vector Bin Packing problem, in which items are multidimensional vectors. We improve over the previous fastest $O^*(k! \cdot 4^k)$ time algorithm. Our algorithm works by reducing the problem to finding an exact weight perfect matching in a (multi-)graph with $O^*(2^k)$ edges, whose weights are integers of the order of $O^*(2^k)$. To solve the matching problem in the desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani algorithm with only a linear dependence on the edge weights and the number of edges, which may be of independent interest. Moreover, we give a tight lower bound, under the Strong Exponential Time Hypothesis (SETH), showing that the constant $2$ in the base of the exponent cannot be further improved for Vector Bin Packing. Our techniques also lead to improved algorithms for Vector Multiple Knapsack, Vector Bin Covering, and Perfect Matching with Hitting Constraints.
