×

zbMATH — the first resource for mathematics

A derivation of Lovász’ theta via augmented Lagrange duality. (English) Zbl 1062.90055
Summary: A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to S. Poljak, F. Rendl and H. Wolkowicz [J. Glob. Optim. 7, No. 1, 51–73 (1995; Zbl 0843.90088)], and further developed C. Lemaréchal and F. Oustry [Semidefinite relaxation and Lagrangian duality with application to combinatorial optimization, Technical Report 3170. INRIA Rhône-Alpes (199); http://www.inria.fr/RRRT/RR-3710.html], 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.
MSC:
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C22 Semidefinite programming
90C46 Optimality conditions and duality in mathematical programming
Software:
SDPpack
PDF BibTeX XML Cite
Full Text: DOI Numdam Numdam EuDML
References:
[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 ). MR 936633 | Zbl 0634.05001 · Zbl 0634.05001
[4] C. Helmberg , Fixing variables in semidefinite relaxations . SIAM J. Matrix Anal. Appl. 21 ( 2000 ) 952 - 969 . MR 1745318 | Zbl 0961.90075 · Zbl 0961.90075
[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 . MR 1367976
[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 . MR 1617152 | Zbl 0910.90262 · Zbl 0910.90262
[7] D. Knuth , The sandwich theorem . Electron. J. Combinatorics 1 ( 1994 ); www.combinatorics.org/Volume_1/volume1.html#A1 arXiv | MR 1269161 | Zbl 0810.05065 · Zbl 0810.05065
[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 . MR 1461382 | Zbl 0888.90128 · Zbl 0888.90128
[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 . MR 514926 | Zbl 0395.94021 · Zbl 0395.94021
[10] L. Lovász , Bounding the independence number of a graph . Ann. Discrete Math. 16 ( 1982 ). MR 686309 | Zbl 0502.05051 · Zbl 0502.05051
[11] L. Lovász and L. Schrijver , Cones of matrices, and set functions and \(0-1\) optimization . SIAM J. Optim. 1 ( 1991 ) 166 - 190 . MR 1098425 | Zbl 0754.90039 · Zbl 0754.90039
[12] S. Poljak , F. Rendl and H. Wolkowicz , A recipe for semidefinite relaxation for \((0-1)\) quadratic programming . J. Global Optim. 7 ( 1995 ) 51 - 73 . MR 1342935 | Zbl 0843.90088 · Zbl 0843.90088
[13] N. Shor , Nondifferentiable Optimization and Polynomial Problems . Kluwer Academic Publishers, Dordrecht, The Netherlands ( 1998 ). MR 1620179 | Zbl 0901.49015 · Zbl 0901.49015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.