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

Mustapha Ç. Pinar

RAIRO - Operations Research (2010)

  • 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 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
  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).  
  4. C. Helmberg, Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl.21 (2000) 952-969.  
  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.  
  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.  
  7. D. Knuth, The sandwich theorem. Electron. J. Combinatorics 1 (1994);  
  8. M. Laurent, S. Poljak and F. Rendl, Connections between semidefinite relaxations of the max-cut and stable set problems. Math. Programming77 (1997) 225-246.  
  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);  URIhttp://www.inria.fr/RRRT/RR-3710.html
  10. L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory25 (1979) 355-381.  
  11. L. Lovász, Bounding the independence number of a graph. Ann. Discrete Math. 16 (1982).  
  12. L. Lovász and L. Schrijver, Cones of matrices, and set functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166-190.  
  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.  
  14. N. Shor, Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998).  

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.