×

zbMATH — the first resource for mathematics

Complexity analyses of Bienstock-Zuckerberg and lasserre relaxations on the matching and stable set polytopes. (English) Zbl 1298.90054
Günlük, Oktay (ed.) et al., Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15–17, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20806-5/pbk). Lecture Notes in Computer Science 6655, 14-26 (2011).
Summary: Many hierarchies of lift-and-project relaxations for \(0,1\) integer programs have been proposed, two of the most recent and strongest being those by J. B. Lasserre in 2001 [Lect. Notes Comput. Sci. 2081, 293–303 (2001; Zbl 1010.90515)], and D. Bienstock and M. Zuckerberg in 2004 [SIAM J. Optim. 15, No. 1, 63–95 (2004; Zbl 1077.90041)]. We prove that, on the LP relaxation of the matching polytope of the complete graph on \((2n+1)\) vertices defined by the nonnegativity and degree constraints, the Bienstock-Zuckerberg operator (even with positive semidefiniteness constraints) requires \(\Theta(\sqrt{n})\) rounds to reach the integral polytope, while the Lasserre operator requires \(\Theta (n)\) rounds. We also prove that the Bienstock-Zuckerberg operator, without the positive semidefiniteness constraint requires approximately \(n/2\) rounds to reach the stable set polytope of the \(n\)-clique, if we start with the fractional stable set polytope. As a by-product of our work, we consider a significantly strengthened version of the Sherali-Adams operator and a strengthened version of the Bienstock-Zuckerberg operator. Most of our results also apply to these stronger operators.
For the entire collection see [Zbl 1216.90002].

MSC:
90C10 Integer programming
90C22 Semidefinite programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aguilera, N.E., Bianchi, S.M., Nasini, G.L.: Lift and project relaxations for the matching and related polytopes. Discrete Appl. Math. 134(1-3), 193–212 (2004) · Zbl 1032.05106
[2] Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89(1-3), 3–44 (1998) · Zbl 0921.90118
[3] Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Programming 58(3, Ser. A), 295–324 (1993) · Zbl 0796.90041
[4] Benabbas, S., Georgiou, K., Magen, A.: The Sherali-Adams system applied to vertex cover: why Borsuk graphs fool strong LPs and some tight integrality gaps for SDPs (2010) (extended Abstract)
[5] Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0-1 integer programming. SIAM J. Optim. 15(1), 63–95 (2004) · Zbl 1077.90041
[6] Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26(1), 19–30 (2001) · Zbl 1073.90574
[7] Cheung, K.K.H.: On Lovász-Schrijver lift-and-project procedures on the Dantzig-Fulkerson-Johnson relaxation of the TSP. SIAM J. Optim. 16(2), 380–399 (2005) · Zbl 1122.90065
[8] Cheung, K.K.H.: Computation of the Lasserre ranks of some polytopes. Math. Oper. Res. 32(1), 88–94 (2007) · Zbl 1278.90331
[9] Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Tight integrality gaps for vertex cover SDPs in the Lovász-Schrijver hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 13(152) (2006) · Zbl 1209.68268
[10] Gouveia, J., Parrilo, P.A., Thomas, R.R.: Theta bodies for polynomial ideals. SIAM Journal on Optimization 20(4), 2097–2118 (2010) · Zbl 1213.90190
[11] Goemans, M.X., Tunçel, L.: When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 26(4), 796–815 (2001) · Zbl 1082.90548
[12] Hong, S.-P., Tunçel, L.: Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra. Discrete Appl. Math. 156(1), 25–41 (2008) · Zbl 1152.90538
[13] Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 293–303. Springer, Heidelberg (2001) · Zbl 1010.90515
[14] Laurent, M.: Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure. SIAM J. Optim. 12(2), 345–375 (2001/2002) · Zbl 1068.90587
[15] Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28(3), 470–496 (2003) · Zbl 1082.90084
[16] Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166–190 (1991) · Zbl 0754.90039
[17] Lipták, L., Tunçel, L.: The stable set problem and the lift-and-project ranks of graphs. Math. Program. 98(1-3, Ser. B), 319–353 (2003); Integer programming (Pittsburgh, PA, 2002) · Zbl 1160.90584
[18] Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: STOC 2009. ACM Press, New York (2009) · Zbl 1304.90144
[19] Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411–430 (1990) · Zbl 0712.90050
[20] Stephen, T., Tunçel, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1), 1–7 (1999) · Zbl 0977.90078
[21] Schoenebeck, G., Trevisan, L., Tulsiani, M.: A linear round lower bound for Lovász-Schrijver SDP relaxations of vertex cover. In: IEEE Conference on Computational Complexity, pp. 6–98. IEEE Computer Society, Los Alamitos (2006)
[22] Zuckerberg, M.: A Set Theoretic Approach to Lifting Procedures for 0,1 Integer Programming. PhD thesis, Columbia University (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.