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

RAIRO - Operations Research (2010)

- Volume: 37, Issue: 1, page 17-27
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topPinar, Mustapha Ç.. "A Derivation of Lovász' Theta via Augmented Lagrange Duality." RAIRO - Operations Research 37.1 (2010): 17-27. <http://eudml.org/doc/105280>.

@article{Pinar2010,

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.
},

author = {Pinar, Mustapha Ç.},

journal = {RAIRO - Operations Research},

keywords = {Lagrange duality; stable set; Lovász theta function;
semidefinite relaxation.; semidefinite relaxation},

language = {eng},

month = {3},

number = {1},

pages = {17-27},

publisher = {EDP Sciences},

title = {A Derivation of Lovász' Theta via Augmented Lagrange Duality},

url = {http://eudml.org/doc/105280},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Pinar, Mustapha Ç.

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

JO - RAIRO - Operations Research

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 1

SP - 17

EP - 27

AB -
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.

LA - eng

KW - Lagrange duality; stable set; Lovász theta function;
semidefinite relaxation.; semidefinite relaxation

UR - http://eudml.org/doc/105280

ER -

## References

top- F. Alizadeh, J.-P. Haberly, V. Nayakkankuppam and M.L. Overton, SDPPACK user's guide, Technical Report 734. NYU Computer Science Department (1997).
- N. Brixius, R. Sheng and F. Potra, SDPHA user's guide, Technical Report. University of Iowa (1998).
- M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1988). Zbl0634.05001
- C. Helmberg, Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl.21 (2000) 952-969. Zbl0961.90075
- C. Helmberg, S. Poljak, F. Rendl and H. Wolkowicz, Combining semidefinite and polyhedral relaxations for integer programs, edited by E. Balas and J. Clausen, Integer Programming and Combinatorial Optimization IV. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci. 920 (1995) 124-134.
- J. Kleinberg and M. Goemans, The Lovász theta function and a semidefinite programming relaxation of vertex cover. SIAM J. Discrete Math.11 (1998) 196-204. Zbl0910.90262
- D. Knuth, The sandwich theorem. Electron. J. Combinatorics 1 (1994); Zbl0810.05065
- M. Laurent, S. Poljak and F. Rendl, Connections between semidefinite relaxations of the max-cut and stable set problems. Math. Programming77 (1997) 225-246. Zbl0888.90128
- C. Lemaréchal and F. Oustry, Semidefinite relaxation and Lagrangian duality with application to combinatorial optimization, Technical Report 3170. INRIA Rhône-Alpes (1999); URIhttp://www.inria.fr/RRRT/RR-3710.html
- L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory25 (1979) 355-381. Zbl0395.94021
- L. Lovász, Bounding the independence number of a graph. Ann. Discrete Math. 16 (1982). Zbl0502.05051
- L. Lovász and L. Schrijver, Cones of matrices, and set functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166-190. Zbl0754.90039
- S. Poljak, F. Rendl and H. Wolkowicz, A recipe for semidefinite relaxation for (0-1) quadratic programming. J. Global Optim.7 (1995) 51-73. Zbl0843.90088
- N. Shor, Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998). Zbl0901.49015

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.