19 citations · 30 across the 11 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
math.CO2011★ 19 cited
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…
cs.DS2011★ 1 cited
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…