An asymptotically exact algorithm for the high-multiplicity bin packing problem
An asymptotically exact algorithm for the high-multiplicity bin packing problem
复制标题
高重数装箱问题的渐近精确算法
作者：
C. Filippi;A. Agnetis
装箱问题包括找出装入一组物品所需的给定容量D的最小箱数，每个箱子都有一定的重量。我们考虑问题的高重数版本，其中只有C个不同的权值。证明了当C=2时，问题可以在O(LogD)时间内求解。对于一般情况，我们给出了一个算法，它提供的解比最优解最多需要C−2个桶，即一个渐近精确的算法。对于固定的C，算法的复杂度为O(poly(LogD))，其中poly(·)是不依赖于C的多项式函数。
The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C−2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly( log D)), where poly(·) is a polynomial function not depending on C.