181 citations · 620 across the 171 of their papers we have counts for
Showing 2014 · cs.CCShow all
2 papers · 2 filters
cs.CC2014
Affine reductions for LPs and SDPs
Gábor Braun, Sebastian Pokutta, Daniel Zink
We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion. Our reduction mechanism is a minor restriction of classical…
cs.CC2014★ 15 cited
The matching polytope does not admit fully-polynomial size relaxation schemes
Gábor Braun, Sebastian Pokutta
The groundbreaking work of Rothvoß [arxiv:1311.2369] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the…