A Derivation of Lovász' Theta via Augmented Lagrange Duality
Bilkent University, Department of Industrial Engineering, 06800 Ankara, Turkey; email@example.com..
A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to Poljak et al. , and further developed in Lemaréchal and Oustry , leads to simple alternative derivations of well-known, important relaxations to two well-known problems of discrete optimization: the maximum stable set problem and the maximum vertex cover problem. The resulting relaxation is easily transformed to the well-known Lovász θ number.
Mathematics Subject Classification: 90C27 / 90C27 / 90C35
Key words: Lagrange duality / stable set / Lovász theta function / semidefinite relaxation.
© EDP Sciences, 2003