A priori optimization for the probabilistic maximum independent set problem

dc.contributor.author	Murat, Cécile
dc.contributor.author	Paschos, Vangelis
dc.date.accessioned	2010-01-12T09:25:34Z
dc.date.available	2010-01-12T09:25:34Z
dc.date.issued	2002
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/2878
dc.language.iso	en	en
dc.subject	Independent set	en
dc.subject	Polynomial approximation	en
dc.subject	NP-hard problem	en
dc.subject	Probabilistic optimization	en
dc.subject.ddc	003	en
dc.title	A priori optimization for the probabilistic maximum independent set problem	en
dc.type	Article accepté pour publication ou publié
dc.description.abstracten	We first propose a formal definition for the concept of probabilistic combinatorial optimization problem (under the a priori method). Next, we study the complexity of optimally solving probabilistic maximum independent set problem under several a priori optimization strategies as well as the complexity of approximating optimal solutions. For the different strategies studied, we present results about the restriction of probabilistic independent set on bipartite graphs.	en
dc.relation.isversionofjnlname	Theoretical Computer Science
dc.relation.isversionofjnlvol	270	en
dc.relation.isversionofjnlissue	1-2	en
dc.relation.isversionofjnldate	2002
dc.relation.isversionofjnlpages	561-590	en
dc.relation.isversionofdoi	http://dx.doi.org/10.1016/S0304-3975(01)00005-6	en
dc.description.sponsorshipprivate	oui	en
dc.relation.isversionofjnlpublisher	Elsevier	en
dc.subject.ddclabel	Recherche opérationnelle	en