81 citations · 136 across the 38 of their papers we have counts for
4 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…
Cover-Decomposition and Polychromatic Numbers
Béla Bollobás, David Pritchard, Thomas Rothvoß +1
A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in…
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…
Prizing on Paths: A PTAS for the Highway Problem
Fabrizio Grandoni, Thomas Rothvoss
In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the…