Geodesic
A derivation of Lovász' theta via augmented Lagrange duality
RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 1, pp. 17-27
Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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.

DOI : 10.1051/ro:2003012
Classification : 90C27, 90C27, 90C35
Keywords: 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},
     year = {2003},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {1},
     doi = {10.1051/ro:2003012},
     zbl = {1062.90055},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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
SP  - 17
EP  - 27
VL  - 37
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2003012/
DO  - 10.1051/ro:2003012
LA  - en
ID  - RO_2003__37_1_17_0
ER  - 
%0 Journal Article
%A Pinar, Mustapha Ç.
%T A derivation of Lovász' theta via augmented Lagrange duality
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2003
%P 17-27
%V 37
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2003012/
%R 10.1051/ro:2003012
%G en
%F RO_2003__37_1_17_0
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

Cité par Sources :