Show simple item record

dc.contributor.authorMurat, Cécile
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-12T09:25:34Z
dc.date.available2010-01-12T09:25:34Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2878
dc.language.isoenen
dc.subjectIndependent seten
dc.subjectPolynomial approximationen
dc.subjectNP-hard problemen
dc.subjectProbabilistic optimizationen
dc.subject.ddc003en
dc.titleA priori optimization for the probabilistic maximum independent set problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol270en
dc.relation.isversionofjnlissue1-2en
dc.relation.isversionofjnldate2002
dc.relation.isversionofjnlpages561-590en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0304-3975(01)00005-6en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record