About: A Derivation of Lovász' Theta via Augmented Lagrange Duality

Documentation

scienceplus.abes.fr version Bêta

scienceplus.abes.fr | explorer

À propos de : A Derivation of Lovász' Theta via Augmented Lagrange Duality Goto Sponge NotDistinct Permalink

Attributs	Valeurs
type	work Article
Is Part Of	http://hub.abes.fr/edp/periodical/ro/2003/volume_37/issue_1/w
Subject	Combinatorial optimization Programming involving graphs or networks Lagrange duality Lovász theta function semidefinite relaxation. stable set
Title	A Derivation of Lovász' Theta via Augmented Lagrange Duality
Date	2003-01-01(xsd:dateTime)
has manifestation of work	http://hub.abes.fr/edp/periodical/ro/2003/volume_37/issue_1/ro2220/m/print http://hub.abes.fr/edp/periodical/ro/2003/volume_37/issue_1/ro2220/m/web
related by	http://hub.abes.fr/edp/periodical/ro/2003/volume_37/issue_1/ro2220/authorship/1
Author	Pinar, Mustapha Ç.
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.
article type	research-article
publisher identifier	ro2220
Date Copyrighted	2003-01-01(xsd:dateTime)
Rights	© EDP Sciences, 2003
Rights Holder	EDP Sciences
is part of this journal	Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle
is primary topic of	http://hub.abes.fr/edp/periodical/ro/2003/volume_37/issue_1/ro2220/w/record

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata