81 citations · 136 across the 38 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CC2013★ 13 cited
The matching polytope has exponential extension complexity
Thomas Rothvoss
A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra v…
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…