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 |