19 citations · 26 across the 5 of their papers we have counts for
5 papers
Lecture Notes on the ARV Algorithm for Sparsest Cut
Thomas Rothvoss
One of the landmarks in approximation algorithms is the -approximation algorithm for the Uniform Sparsest Cut problem by Arora, Rao and Vazirani from 2004. The al…
A Logarithmic Additive Integrality Gap for Bin Packing
Rebecca Hoberg, Thomas Rothvoss
For bin packing, the input consists of items with sizes which have to be assigned to a minimum number of bins of size 1. Recently, the second author gav…
A simpler proof for O(congestion + dilation) packet routing
Thomas Rothvoss
In the store-and-forward routing problem, packets have to be routed along given paths such that the arrival time of the latest packet is minimized. A groundbreaking result of Leigh…
Some 0/1 polytopes need exponential size extended formulations
Thomas Rothvoß
We prove that there are 0/1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a sets X \subseteq {0,1}^n such that conv(X) mu…
The Entropy Rounding Method in Approximation Algorithms
Thomas Rothvoss
Let A be a matrix, c be any linear objective function and x be a fractional vector, say an LP solution to some discrete optimization problem. Then a recurring task in theoretical c…