Strong reductions for extended formulations
- 25 August 2018
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 172 (1-2) , 591-620
Abstract
No abstract availableKeywords
Funding Information
- Directorate for Engineering (CMMI-1452463)
This publication has 19 references indexed in Scilit:
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs2017
- Inapproximability of Combinatorial Problems via Small LPs and SDPs2015
- Approximate Constraint Satisfaction Requires Large LP Relaxations2013
- Sparsest cut on bounded treewidth graphs2013
- Approximation Limits of Linear Programs (Beyond Hierarchies)2012
- Optimal Long Code Test with One Free Bit2009
- Integrality gaps for Sherali-Adams relaxations2009
- Linear Level Lasserre Lower Bounds for Certain k-CSPs2008
- Euclidean distortion and the sparsest cutJournal of the American Mathematical Society, 2007
- ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUTcomputational complexity, 2006