Proving Integrality Gaps without Knowing the Linear Program
by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis
Theory of Computing, Volume 2(2), pp. 19-51, 2006
Bibliography with links to cited articles
| [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. [ .ps ] |
| [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 ln n for approximating set cover.
Journal of the ACM, 45(4):634-652, 1998.
[JACM:285055.285059]. [ http ] |
| [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]. [ http ] |
| [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. [ http ] |
| [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]. [ .ps ] |
| [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. [ .ps ] |
| [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]. |
This file has been generated by bibtex2html 1.74