When Does the Positive Semidefiniteness Constraint Help In Lifting Procedures

Simple item page
dc.creatorTuncel, Levent
dc.creatorGoemans, Michel X.
dc.date2000-06-05
dc.date.accessioned2026-07-07T04:35:44Z
dc.date.available2026-07-07T04:35:44Z
dc.descriptionWe study the lift-and-project procedures of Lovász and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, in the worst case. Various examples are considered. We also provide geometric conditions characterizing when the positive semidefiniteness constraint does not help.
dc.description24 pages, 3 images
dc.identifierhttps://arxiv.org/abs/math/0006036
dc.identifierhttp://arxiv.org/abs/math/0006036
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/59354
dc.subjectCombinatorics
dc.subjectOperator Algebras
dc.titleWhen Does the Positive Semidefiniteness Constraint Help In Lifting Procedures
dc.typetext

Files

Collections

arXiv