On a representation of the matching polytope via semidefinite liftings

Authors
Stephen, T Tuncel, L
Citation
T. Stephen et L. Tuncel, On a representation of the matching polytope via semidefinite liftings, MATH OPER R, 24(1), 1999, pp. 1-7
Citations number
3
Categorie Soggetti
Mathematics
Journal title
MATHEMATICS OF OPERATIONS RESEARCH
ISSN journal
0364765X → ACNP
Volume
24
Issue
1
Year of publication
1999
Pages
1 - 7
Database
ISI
SICI code
0364-765X(199902)24:1<1:OAROTM>2.0.ZU;2-3
Abstract
We consider the relaxation of the matching polytope defined by the non-nega tivity and degree constraints We prove that given an undirected graph on n nodes and the corresponding relaxation of the matching polytope, right perp endicular n/2 left perpendicular iterations of the Lovasz-Schrijver semidef inite lifting procedure are needed to obtain the matching polytope. in the worst case. We show that right perpendicular n/2 left perpendicular iterati ons of the procedure always suffice.