A Derivation of Lovász' Theta via Augmented Lagrange Duality

Bilkent University, Department of Industrial Engineering, 06800 Ankara, Turkey; mustafap@bilkent.edu.tr..

Received: July 2002

Abstract

A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to Poljak et al. [13], and further developed in Lemaréchal and Oustry [9], 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.