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
topAbstract
topHow 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).
- C. Helmberg, Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl.21 (2000) 952-969.
- 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.
- D. Knuth, The sandwich theorem. Electron. J. Combinatorics 1 (1994);
- M. Laurent, S. Poljak and F. Rendl, Connections between semidefinite relaxations of the max-cut and stable set problems. Math. Programming77 (1997) 225-246.
- 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.
- L. Lovász, Bounding the independence number of a graph. Ann. Discrete Math. 16 (1982).
- L. Lovász and L. Schrijver, Cones of matrices, and set functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166-190.
- S. Poljak, F. Rendl and H. Wolkowicz, A recipe for semidefinite relaxation for (0-1) quadratic programming. J. Global Optim.7 (1995) 51-73.
- N. Shor, Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998).
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.