Approximation Limits of Linear Programs (Beyond Hierarchies)
arXiv:1204.0957
Abstract
We develop a framework for approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1/2-eps})-approximations for CLIQUE require linear programs of size 2^{n^Ω(eps)}. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem.) Moreover, we establish a similar result for approximations of semidefinite programs by linear programs. Our main ingredient is a quantitative improvement of Razborov's rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjointness matrix.
23 pages, 2 figures
References in corpus (2)
Cited by in corpus (11)
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- The matching polytope does not admit fully-polynomial size relaxation schemes
- The matching polytope has exponential extension complexity
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Generalised probabilistic theories and conic extensions of polytopes
- Lower bounds on the size of semidefinite programming relaxations
- Exponential lower bounds on the size of approximate formulations in the natural encoding for Capacitated Facility Location
- Integrality gaps for strengthened LP relaxations of Capacitated and Lower-Bounded Facility Location
- Uncapacitated Flow-based Extended Formulations
- Polynomial size linear programs for problems in P