Optimization Online


Lift-and-project ranks and antiblocker duality

Laszlo Liptak (liptak***at***oakland.edu)
Levent Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: Recently, Aguilera et al.\ exposed a beautiful relationship between antiblocker duality and the lift-and-project operator proposed by Balas et al. We present a very short proof of their result that the \BCC-rank of the clique polytope is invariant under complementation. The proof of Aguilera et al. relies on their main technical result, which describes a stronger duality property of all intermediate relaxations. We provide a short proof of this result, too, using simpler and more general arguments. As a result, our theorems are slightly more general. We conclude by proving that such properties do not extend to the $N_0$ and $N$ procedures of Lov\'asz and Schrijver, or to the $N_+$ procedure unless $\cP = \cNP$.

Keywords: stable set problem, antiblocker duality,lift-and-project, semidefinite lifting,integer programming, perfect graphs

Category 1: Combinatorial Optimization

Citation: Research Report CORR 2003-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, July 2003

Download: [Postscript]

Entry Submitted: 07/12/2003
Entry Accepted: 07/12/2003
Entry Last Modified: 07/22/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society