Access Restriction

Author Chan, Siu On ♦ Lee, James R. ♦ Raghavendra, Prasad ♦ Steurer, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword LP hierarchies ♦ Linear programming, extended formulations ♦ Approximation complexity ♦ Constraint satisfaction problems ♦ Lower bounds
Abstract We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are no more powerful than programs arising from a constant number of rounds of the Sherali--Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of ½ and any such linear program for Max 3-Sat has an integrality gap of ⅞.
Description Author Affiliation: University of California, Berkeley (Raghavendra, Prasad); University of Washington (Lee, James R.); Chinese University of Hong Kong (Chan, Siu On); Cornell University (Steurer, David)
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 4
Page Count 22
Starting Page 1
Ending Page 22

Open content in new tab

   Open content in new tab
Source: ACM Digital Library