Voir la notice de l'article provenant de la source Numdam
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.
@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://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 :