Approximation Limits of Linear Programs (Beyond Hierarchies)

• 成果类型: Article
• 署名作者: Braun, Gabor; Fiorini, Samuel; Pokutta, Sebastian; Steurer, David
• 署名单位: University System of Georgia; Georgia Institute of Technology; Universite Libre de Bruxelles; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0694
• 发表日期: 2015
• 页码: 756-772
• 关键词: Communication complexity; integrality gaps; lovasz-schrijver; sherali-adams; relaxations; cut; csps; cone; sets; rank

摘要

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n(1/2-is an element of))-approximations for CLIQUE require LPs of size 2(n Omega(is an element of)). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.