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.
Classification : 90C27, 90C27, 90C35
Mots clés : Lagrange duality, stable set, Lovász theta function, semidefinite relaxation
@article{RO_2003__37_1_17_0,
author = {Pinar, Mustapha \c{C}.},
title = {A derivation of {Lov\'asz'} theta via augmented {Lagrange} duality},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {17--27},
publisher = {EDP-Sciences},
volume = {37},
number = {1},
year = {2003},
doi = {10.1051/ro:2003012},
zbl = {1062.90055},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2003012/}
}
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 DA - 2003/// SP - 17 EP - 27 VL - 37 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2003012/ UR - https://zbmath.org/?q=an%3A1062.90055 UR - https://doi.org/10.1051/ro:2003012 DO - 10.1051/ro:2003012 LA - en ID - RO_2003__37_1_17_0 ER -
Pinar, Mustapha Ç. A derivation of Lovász' theta via augmented Lagrange duality. RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 1, pp. 17-27. doi : 10.1051/ro:2003012. http://www.numdam.org/articles/10.1051/ro:2003012/
[1] ,, and, SDPPACK user's guide, Technical Report 734. NYU Computer Science Department (1997).
[2] , and, SDPHA user's guide, Technical Report. University of Iowa (1998).
[3] , and, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1988). | MR 936633 | Zbl 0634.05001
[4] , Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21 (2000) 952-969. | MR 1745318 | Zbl 0961.90075
[5] ,, and, 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] and, 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
[7] , The sandwich theorem. Electron. J. Combinatorics 1 (1994); www.combinatorics.org/Volume_1/volume1.html#A1 | MR 1269161 | Zbl 0810.05065
[8] , and, Connections between semidefinite relaxations of the max-cut and stable set problems. Math. Programming 77 (1997) 225-246. | MR 1461382 | Zbl 0888.90128
[9] and, 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] , On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 (1979) 355-381. | MR 514926 | Zbl 0395.94021
[11] , Bounding the independence number of a graph. Ann. Discrete Math. 16 (1982). | MR 686309 | Zbl 0502.05051
[12] and, Cones of matrices, and set functions and optimization. SIAM J. Optim. 1 (1991) 166-190. | MR 1098425 | Zbl 0754.90039
[13] , and, A recipe for semidefinite relaxation for quadratic programming. J. Global Optim. 7 (1995) 51-73. | MR 1342935 | Zbl 0843.90088
[14] , Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998). | MR 1620179 | Zbl 0901.49015
Cité par Sources :
