34 citations · 60 across the 20 of their papers we have counts for
3 papers · 1 filter
Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps
Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß +1
We consider set covering problems where the underlying set system satisfies a particular replacement property w.r.t. a given partial order on the elements: Whenever a set is in the…
Covering Cubes and the Closest Vector Problem
Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier
We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity norm. The running time of our method depends on the d…
Bin Packing via Discrepancy of Permutations
Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß
A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmark…