81 citations · 136 across the 38 of their papers we have counts for
Showing 2013 · cs.DSShow all
2 papers · 2 filters
cs.DS2013
Polynomiality for Bin Packing with a Constant Number of Item Types
Michel X. Goemans, Thomas Rothvoss
We consider the bin packing problem with d different item sizes s_i and item multiplicities a_i, where all numbers are given in binary encoding. This problem formulation is also kn…
cs.DS2013
Approximating Bin Packing within O(log OPT * log log OPT) bins
Thomas Rothvoss
For bin packing, the input consists of n items with sizes s_1,...,s_n in [0,1] which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm…