Approximating Bin Packing within O(log OPT * Log Log OPT) Bins
Approximating Bin Packing within O(log OPT * Log Log OPT) Bins
复制标题
近似 O(log OPT * Log Log OPT) Bin 内的装箱
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
T. Rothvoss
中科院分区：
文献类型：
--
作者：
T. Rothvoss
对于装箱，输入由n个大小在0到1之间的物品组成，这些物品必须分配给最小数量的大小为1的物品。1982年开创性的Karmarkar-Karp算法产生的解最多具有OPT + O（log2 OPT）个bin。我们提供了30年来的第一个改进，并表明可以在多项式时间内找到代价为OPT + O（log OPT * log log OPT）的解。这是通过使用差异理论中的熵法对Gilmore-Gomory LP松弛的分数解进行舍入来实现的。通过Bansal和Lovett-Meka算法，结果是建设性的。
For bin packing, the input consists of n items with sizes between 0 and 1, which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm from '82 produces a solution with at most OPT + O(log2 OPT) bins. We provide the first improvement in now 3 decades and show that one can find a solution of cost OPT + O(log OPT * log log OPT) in polynomial time. This is achieved by rounding a fractional solution to the Gilmore-Gomory LP relaxation using the Entropy Method from discrepancy theory. The result is constructive via algorithms of Bansal and Lovett-Meka.