Volume 37, Number 1, January-March 2003
|Page(s)||17 - 27|
|Published online||15 November 2003|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.