Approximation Limits of Linear Programs (Beyond Hierarchies)

Details Approximation Limits of Linear Programs (Beyond Hierarchies) Approximation Limits of Linear Programs (Beyond Hierarchies)

2012-04-04

arxiv.org/abs/1204.0957v1

Computer Science

Computational Complexity

30 pages, 1 figure, conference version

Scientific paper

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^\Omega(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.

Affiliated with

Also associated with

No associations

Rating

Approximation Limits of Linear Programs (Beyond Hierarchies) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Limits of Linear Programs (Beyond Hierarchies), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Limits of Linear Programs (Beyond Hierarchies) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32311