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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.