No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ

References

• Arora S, Bollobás B, Lovász L (2002) Proving integrality gaps without knowing the linear program. Chazelle B, ed. Proc. 43rd Sympos. on Foundations of Computer Science (IEEE Computer Society, New York), 313–322.Google Scholar
• Arora S, Bollobás B, Lovász L, Tourlakis I (2006) Proving integrality gaps without knowing the linear program. Theory Comput. 2:19–51.Crossref, Google Scholar
• Bansal N, Khot S (2009) Optimal long code test with one free bit. Spielman DA, ed. Proc. 50th Sympos. on Foundations of Computer Science (IEEE Computer Society, Los Alamitos), 453–462.Google Scholar
• Barak B, Chan SO, Kothari PK (2015) Sum of squares lower bounds from pairwise independence. Indyk P, ed. Proc. 26th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 97–106.Google Scholar
• Benabbas S, Georgiou K, Magen A, Tulsiani M (2012) SDP gaps from pairwise independence. Theory Comput. 8(12):269–289.Crossref, Google Scholar
• Bhaskara A, Charikar M, Vijayaraghavan A, Guruswami V, Zhou Y (2012) Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. Rabani Y, ed. Proc. 23rd ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 388–405.Google Scholar
• Bienstock D (2008) Approximate formulations for 0-1 knapsack sets. Oper. Res. Lett. 36(3):317–320.Crossref, Google Scholar
• Braun G, Pokutta S (2016) Common information and unique disjointness. Algorithmica 76(3):597–629.Crossref, Google Scholar
• Braun G, Pokutta S, Zink D (2015) Inapproximability of combinatorial problems via small LPs and SDPs. Rubinfeld R, ed. Proc. 47th ACM Sympos. on Theory of Computing (ACM, New York), 107–116.Google Scholar
• Braun G, Roy A, Pokutta S (2016) Stronger reductions for extended formulations. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming and Combinatorial Optimization (Springer International, Berlin, Heidelberg), 350–361.Google Scholar
• Braun G, Fiorini S, Pokutta S, Steurer D (2015) Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3):756–772.Link, Google Scholar
• Briët J, Dadush D, Pokutta S (2015) On the existence of 0/1 polytopes with high semidefinite extension complexity. Math. Program. 153(1):179–199.Crossref, Google Scholar
• Chan SO, Lee JR, Raghavendra P, Steurer D (2013) Approximate constraint satisfaction requires large LP relaxations. Boneh D, Roughgarden T, eds. Proc. 54th Sympos. on Foundations of Computer Science (IEEE Computer Society, Los Alamitos), 350–359.Google Scholar
• Charikar M, Makarychev K, Makarychev Y (2009) Integrality gaps for Sherali–Adams relaxations. Spielman DA, ed. Proc. 41st ACM Sympos. on Theory of Computing (ACM, New York), 283–292.Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2010) Extended formulations in combinatorial optimization. Quart. J. Oper. Res. 8(1):1–48.Crossref, Google Scholar
• de la Vega WF, Kenyon-Mathieu C (2007) Linear programming relaxations of Maxcut. Gabow H, ed. Proc. 23rd ACM-SIAM Sympos. on Discrete Algorithms (ACM, New York), 53–61.Google Scholar
• Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann. Math. 162(1):439–485.Crossref, Google Scholar
• Feige U, Jozeph S (2014) Demand queries with preprocessing. Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, eds. Proc. 41st Internat. Colloquium on Automata, Languages, and Programming (Springer-Verlag, Berlin, Heidelberg), 477–488.Google Scholar
• Feige U, Goldwasser S, Lovász L, Safra S, Szegedy M (1996) Interactive proofs and the hardness of approximating cliques. J. ACM 43(2):268–292.Crossref, Google Scholar
• Fiorini S, Massar S, Pokutta S, Tiwary HR, de Wolf R (2015) Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2):Article 17.Crossref, Google Scholar
• Georgiou K, Magen A (2008) Limitations of the Sherali–Adams lift and project system: Compromising local and global arguments. Technical Report CSRG-587.Google Scholar
• Georgiou K, Magen A, Tulsiani M (2009) Optimal Sherali–Adams gaps from pairwise independence. Dinur I, Jansen K, Naor J, Rolim J, eds. Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (Springer-Verlag, Berlin, Heidelberg), 125–139.Google Scholar
• Georgiou K, Magen A, Pitassi T, Tourlakis I (2010) Integrality gaps of 2 − o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy. SIAM J. Comput. 39(8):3553–3570.Crossref, Google Scholar
• Håstad J (1999) Clique is hard to approximate within n1−ϵ. Acta Math. 182(1):105–142.Crossref, Google Scholar
• Hochbaum D (1997) Approximating covering and packing problems: Set cover, vertex cover, independent set and related problems. Hochbaum D, ed. Approximation Algorithms for NP-Hard Problems (PWS Publishing Company, Boston), 94–143.Google Scholar
• Kaibel V (2011) Extended formulations in combinatorial optimization. Optima 85(85):2–7.Google Scholar
• Kaibel V, Pashkovich K, Theis DO (2010) Symmetry matters for the sizes of extended formulations. Eisenbrand F, Shepherd FB, eds. Proc. 14th Conf. on Integer Programming and Combinatorial Optimization (Springer International, Lausanne, Switzerland), 135–148.Google Scholar
• Karlin AR, Mathieu C, Nguyen CT (2011) Integrality gaps of linear and semi-definite programming relaxations for knapsack. Günlük O, Woeginger GJ, eds. Proc. 15th Conf. on Integer Programming and Combinatorial Optimization (Springer International, New York), 301–314.Google Scholar
• Khot S (2002) On the power of unique 2-prover 1-round games. Reif JH, eds. Proc. 34th ACM Sympos. on Theory of Computing (ACM, New York), 767–775.Google Scholar
• Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 − ɛ. J. Comput. System Sci. 74(3):335–349.Crossref, Google Scholar
• Khot S, Saket R (2009) SDP integrality gaps with local ℓ1-embeddability. Spielman DA, eds. Proc. 50th Sympos. on Foundations of Computer Science (IEEE Computer Science, Los Alamitos), 565–574.Google Scholar
• Kothari P, Meka R, Raghavendra P (2017) Approximating rectangles by juntas and weakly-exponential lower bounds for lp relaxations of csps. Hatami H, McKenzie P, King V, eds. Proc. 49th ACM Sympos. on Theory of Computing (ACM, New York), 590–603.Google Scholar
• Lasserre JB (2001) An explicit exact SDP relaxation for nonlinear 0-1 programs. Aardal K, ed. Proc. 8th Conf. on Integer Programming and Combinatorial Optimization (Springer International, Berlin, Heidelberg), 293–203.Google Scholar
• Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• Lee JR, Raghavendra P, Steurer D (2015) Lower bounds on the size of semidefinite programming relaxations. Rubinfeld R, ed. Proc. 47th ACM Sympos. on Theory of Computing (ACM, New York), 567–576.Google Scholar
• Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2):166–190.Crossref, Google Scholar
• Mark B, Ankur M (2013) An information complexity approach to extended formulations. Proc. 45th ACM Sympos. on Theory of Computing (ACM, New York), 161–170.Google Scholar
• Mossel E, O’Donnell R, Oleszkiewicz K (2010) Noise stability of functions with low influences: Invariance and optimality. Ann. Math. 171(1):295–341.Crossref, Google Scholar
• O’Donnell R (2014) Analysis of Boolean Functions (Cambridge University Press, New York).Crossref, Google Scholar
• Parrilo P (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology, Pasadena.Google Scholar
• Pashkovich K (2012) Extended formulations for combinatorial polytopes. Ph.D. thesis, Magdeburg Universität, Magdeburg, Germany.Google Scholar
• Raghavendra P, Steurer D (2009) Integrality gaps for strong SDP relaxations of unique games. Spielman DA, ed. Proc. 50th Sympos. on Foundations of Computer Science (IEEE Computer Science, Los Alamitos), 575–585.Google Scholar
• Rothvoß T (2013) Some 0/1 polytopes need exponential size extended formulations. Math. Program. 142(1–2):255–268.Crossref, Google Scholar
• Rothvoß T (2014) The matching polytope has exponential extension complexity. Karloff H, ed. Proc. 46th ACM Sympos. on Theory of Computing (ACM, New York), 263–272.Google Scholar
• Schoenebeck G (2008) Linear level Lasserre lower bounds for certain k-CSPs. Ravi R, ed. Proc. 49th Sympos. on Foundations of Computer Science (IEEE Computer Science, Los Alamitos), 593–602.Google Scholar
• Schoenebeck G, Trevisan L, Tulsiani M (2007) Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut. Feige U, ed. Proc. 39th ACM Sympos. on Theory of Computing (ACM, New York), 302–310.Google Scholar
• Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430.Crossref, Google Scholar
• Singh M (2010) Bellairs workshop on approximation algorithms. Open problem session #1.Google Scholar
• Svensson O (2013) Hardness of vertex deletion and project scheduling. Theory Comput. 9(24):759–781.Crossref, Google Scholar
• Tulsiani M (2009) CSP gaps and reductions in the Lasserre hierarchy. Srinivasan A, ed. Proc. 41st ACM Sympos. on Theory of Computing (ACM, New York), 303–312.Google Scholar
• Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci. 43(3):441–466.Crossref, Google Scholar