# A derivation of Lovász’ theta via augmented Lagrange duality

RAIRO - Operations Research - Recherche Opérationnelle (2003)

- 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 - Recherche Opérationnelle 37.1 (2003): 17-27. <http://eudml.org/doc/245508>.

@article{Pinar2003,

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 $\theta $ number.},

author = {Pinar, Mustapha Ç.},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

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

language = {eng},

number = {1},

pages = {17-27},

publisher = {EDP-Sciences},

title = {A derivation of Lovász’ theta via augmented Lagrange duality},

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

volume = {37},

year = {2003},

}

TY - JOUR

AU - Pinar, Mustapha Ç.

TI - A derivation of Lovász’ theta via augmented Lagrange duality

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2003

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 $\theta $ number.

LA - eng

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

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

ER -

## References

top- [1] F. Alizadeh, J.-P. Haberly, V. Nayakkankuppam and M.L. Overton, SDPPACK user’s guide, Technical Report 734. NYU Computer Science Department (1997).
- [2] N. Brixius, R. Sheng and F. Potra, SDPHA user’s guide, Technical Report. University of Iowa (1998).
- [3] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1988). Zbl0634.05001MR936633
- [4] C. Helmberg, Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21 (2000) 952-969. Zbl0961.90075MR1745318
- [5] 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. MR1367976
- [6] 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.90262MR1617152
- [7] D. Knuth, The sandwich theorem. Electron. J. Combinatorics 1 (1994); www.combinatorics.org/Volume_1/volume1.html#A1 Zbl0810.05065MR1269161
- [8] M. Laurent, S. Poljak and F. Rendl, Connections between semidefinite relaxations of the max-cut and stable set problems. Math. Programming 77 (1997) 225-246. Zbl0888.90128MR1461382
- [9] C. Lemaréchal and F. Oustry, Semidefinite relaxation and Lagrangian duality with application to combinatorial optimization, Technical Report 3170. INRIA Rhône-Alpes (1999); http://www.inria.fr/RRRT/RR-3710.html
- [10] L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 (1979) 355-381. Zbl0395.94021MR514926
- [11] L. Lovász, Bounding the independence number of a graph. Ann. Discrete Math. 16 (1982). Zbl0502.05051MR686309
- [12] L. Lovász and L. Schrijver, Cones of matrices, and set functions and $0-1$ optimization. SIAM J. Optim. 1 (1991) 166-190. Zbl0754.90039MR1098425
- [13] 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.90088MR1342935
- [14] N. Shor, Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998). Zbl0901.49015MR1620179

## NotesEmbed ?

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