[1]   Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis: Towards strong nonapproximability results in the Lov ász-Schrijver hierarchy. In Proceedings of the 37th Annual Symposium on the Theory of Computing, New York, May 2005. ACM Press. [STOC:1060590.1060634].

[2]   Noga Alon and Joel H. Spencer: The probabilistic method. Wiley, New York, 1992.

[3]   Sanjeev Arora, Béla Bollobás, and László Lovász: Proving integrality gaps without knowing the linear program. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS-02), pp. 313–322, Los Alamitos, November  16–19 2002. [FOCS:10.1109/SFCS.2002.1181954].

[4]   Béla Bollobás: Modern graph theory, volume 184 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1998.

[5]   Maria Bonet, Toniann Pitassi, and Ran Raz: Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic, 62(3):708–728, September 1997.

[6]   Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi: Rank bounds and integrality gaps for cutting planes procedures. In Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, 11–14 October 2003, Cambridge, Massachusetts, pp. 318–327. pub-IEEE, 2003.

[7]   Joseph Cheriyan and Fei Qian: Personal communication, 2005.

[8]   Vasek Chvátal: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math., 4:305–337, 1973.

[9]   William Cook and Sanjeeb Dash: On the matrix-cut rank of polyhedra. Mathematics of Operations Research, 26(1):19–30, 2001.

[10]   Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. In ACM, editor, Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing, San Diego, CA, USA, June 9–11, 2003, pp. 595–601, New York, NY, USA, 2003. ACM Press. [STOC:780542.780629].

[11]   Irit Dinur and Shmuel Safra: On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1), 2005.

[12]   Paul Erdös: Graph theory and probability. Canadian Journal of Mathematics, 11:34–38, 1959.

[13]   Paul Erdös: On circuits and subgraphs of chromatic graphs. Mathematika, 9:170–175, 1962.

[14]   Uriel Feige: Randomized graph products, chromatic numbers, and the Lovász ϑ-function. Combinatorica, 17(1):79–90, 1997. [Combinatorica:x785787h43724566].

[15]   Uriel Feige: A threshold of lnn for approximating set cover. Journal of the ACM, 45(4):634–652, 1998. [JACM:285055.285059].

[16]   Uriel Feige and Robert Krauthgamer: The probable value of the Lovász–Schrijver relaxations for maximum independent set. SIAM Journal on Computing, 32(2):345–370, 2003. [SICOMP:10.1137/S009753970240118X].

[17]   Michel X. Goemans: Worst-case comparison of valid inequalities for the TSP. Mathematical Programming, 69:335–349, 1995. [MathProg:n25193135v44l625].

[18]   Michel X. Goemans and Levent Tunçel: When does the positive semidefiniteness constraint help in lifting procedures? Mathematics of Operations Research, 26(4):796–815, 2001.

[19]   Michel X. Goemans and David P. Williamson: .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC’94 (Montréal, Québec, Canada, May 23-25, 1994), pp. 422–431, New York, 1994. ACM Press. [STOC:195058.195216].

[20]   Johan Håstad: Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001. [JACM:258533.258536].

[21]   Dorit Hochbaum: Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems. In Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997.

[22]   Dorit Hochbaum, editor. Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997.

[23]    László Lipták and László Lovász: Critical facets of the stable set polytope. Combinatorica, 21(1):61–88, 2001. [Combinatorica:8hmkpcvb5qaw5dnv].

[24]   László Lovász and Alexander Schrijver: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization, 1(2):166–190, May 1991. [SIOPT:01/0801013].

[25]   Christos H. Papadimitriou and Santosh Vempala: On the approximability of the Traveling Salesman problem. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC’2000 (Portland, Oregon, May 21-23, 2000), pp. 126–133, New York, 2000. ACM Press. [STOC:335305.335320].

[26]   Fei Qian: The integrality gap of the minimum vertex cover problem. Master’s thesis, University of Waterloo, 2003.

[27]   Alexander A. Razborov: Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR, 281(4):798–801, 1985. In Russian: English translation in Soviet Math. Dokl. 31:354–357, 1985.

[28]   Hanif D. Sherali and Warren P. Adams: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, 3(3):411–430, August 1990. [SIDMA:03/0403036].

[29]   David B. Shmoys: Cut problems and their application to divide-and-conquer. In Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997.

[30]   Iannis Tourlakis: Towards optimal integrality gaps for hypergraph vertex cover in the Lovász-Schrijver hierarchy. In 8th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 9th International Workshop on Randomization and Computation, pp. 233–244, 2005.

[31]   Vijay V. Vazirani: Approximation Algorithms. Springer-Verlag, Berlin, 2001.

[32]   Laurence A. Wolsey: Heuristic analysis, linear programming, and branch and bound. Mathematical Programming Studies, 13:121–134, 1980.

[33]   Mihalis Yannakakis: Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441–466, December 1991. [JCSS:10.1016/0022-0000(91)90024-Y].