When Does the Positive Semidefiniteness Constraint Help In Lifting Procedures

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We 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.
24 pages, 3 images

Keywords

Combinatorics, Operator Algebras

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/59354

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0006036
 http://arxiv.org/abs/math/0006036

Collections

arXiv