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

Mustapha Ç. Pinar

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

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

Abstract

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

How to cite

top

Pinar, 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. [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. [2] N. Brixius, R. Sheng and F. Potra, SDPHA user’s guide, Technical Report. University of Iowa (1998). 
  3. [3] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1988). Zbl0634.05001MR936633
  4. [4] C. Helmberg, Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21 (2000) 952-969. Zbl0961.90075MR1745318
  5. [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. [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. [7] D. Knuth, The sandwich theorem. Electron. J. Combinatorics 1 (1994); www.combinatorics.org/Volume_1/volume1.html#A1 Zbl0810.05065MR1269161
  8. [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. [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. [10] L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 (1979) 355-381. Zbl0395.94021MR514926
  11. [11] L. Lovász, Bounding the independence number of a graph. Ann. Discrete Math. 16 (1982). Zbl0502.05051MR686309
  12. [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. [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. [14] N. Shor, Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998). Zbl0901.49015MR1620179

NotesEmbed ?

top

You must be logged in to post comments.