Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

References

• Balas E., Ceria S., Cornuéjols G. A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Programming (1993) 58:295–324Crossref, Google Scholar
• Bannai I., Ito T.Algebraic Combinatorics I. Association Schemes (1984) (Benjamin/Cummings, London, U.K., Tokyo, Japan) Google Scholar
• Cook W., Dash S. On the matrix-cut rank of polyhedra. Math. Oper. Res. (2001) 26:19–30Link, Google Scholar
• Curto R. E., Fialkow L. A. The truncated complex K-moment problem. Trans. Amer. Math. Soc. (2000) 352:2825–2855Crossref, Google Scholar
• Dash S. On the matrix cuts of Lovász and Schrijver and their use in integer programming. (2000) . Ph.D. thesis, Rice University, Houston, TXGoogle Scholar
• Deza M. M., Laurent M.Geometry of Cuts and Metrics (1997) (Springer Verlag, Berlin) Crossref, Google Scholar
• Goemans M. X., Tunçel L. When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. (2001) 26:796–815Link, Google Scholar
• Grigoriev D. Complexity of positivstellensatz proofs for the knapsack. Comput. Complexity (2001) 10:139–154( http://eccc.uni-trier.de/eccc)Crossref, Google Scholar
• Grigoriev D., Hirsch E. A., Pasechnik D. V. Complexity of semi-algebraic proofs. Electronic Colloquium Comput. Complexity (2001) . Report No. 103Google Scholar
• Horn R. A., Johnson J. C.Matrix Analysis (1990) (Cambridge University Press, Cambridge, U.K.) Google Scholar
• Lasserre J. B. Global optimization with polynomials and the problem of moments. SIAM J. Optim. (2001a) 11:796–817Crossref, Google Scholar
• Lasserre J. B., Aardal K., Gerards A. M. H. An explicit exact SDP relaxation for nonlinear 0–1 programs. Lecture Notes in Computer Science, No. 2081 (2001b) (Springer-Verlag, Berlin) 293–303Crossref, Google Scholar
• Lasserre J. B. An explicit equivalent positive semidefinite program for nonlinear 0–1 programs. SIAM J. Optim. (2002) 12:756–769Crossref, Google Scholar
• Laurent M. Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure. SIAM J. Optim. (2001) 12:345–375Crossref, Google Scholar
• Laurent M. A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0–1 programming. Math. Oper. Res. (2003a) 28:470–496Link, Google Scholar
• Laurent M., Grötschel M. Semidefinite relaxations for Max-Cut. The Sharpest Cut, Festschrift in Honor of M. Padberg's 60th Birthday (2003b) (SIAM, Philadelphia, PA) 291–327MPS-SIAM Series on OptimizationGoogle Scholar
• Lovász L., Schrijver A. Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. (1991) 1:166–190Crossref, Google Scholar
• Nesterov Y., Frenk J. B. G., Roos C., Terlaky T., Zhang S. Squared functional systems and optimization problems. High Performance Optimization (2000) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 405–440Crossref, Google Scholar
• Parrilo P. A. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. (2000) . Ph.D. thesis, California Institute of Technology, Pasadena, CAGoogle Scholar
• Parrilo P. A. Semidefinite programming relaxations for semialgebraic problems. Math. Programming (2003) 96:293–320Crossref, Google Scholar
• Petkovsek M., Wilf H. S., Zeilberger D.A = B (1996) (A. K. Peters, Wellesley, MA) Crossref, Google Scholar
• Putinar M. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. (1993) 42:969–984Crossref, Google Scholar
• Robertson N., Seymour P. D.Graph minors XX: Wagner's Conjecture (1988) . PreprintGoogle Scholar
• 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. (1990) 3:411–430Crossref, Google Scholar
• Sherali H. D., Adams W. P.A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems (1999) (Kluwer, Boston, MA) Crossref, Google Scholar
• Shor N. Z. An approach to obtaining global extremums in polynomial mathematical programming problems. Kibernetika (1987) 5:102–106Google Scholar
• Stephen T., Tunçel L. On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. (1999) 24:1–7Link, Google Scholar
• van Lint J. H., Wilson R. M.A Course in Combinatorics (1992) (Cambridge University Press, Cambridge, MA) Google Scholar