Show simple item record

Probabilistic optimization in graph-problems

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMurat, Cécile
dc.date.accessioned2010-04-27T07:38:10Z
dc.date.available2010-04-27T07:38:10Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4001
dc.language.isoenen
dc.subjectGraphsen
dc.subject.ddc003en
dc.titleProbabilistic optimization in graph-problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study a probabilistic optimization model for graph-problems under vertex-uncertainty. We assume that any vertex vi of the input-graph G(V,E) has only a probability pi to be present in the final graph to be optimized (i.e., the final instance for the problem tackled will be only a sub-graph of the initial graph). Under this model, the original "deterministic" problem gives rise to a new (deterministic) problem on the same input-graph G, having the same set of feasible solutions as the former one, but its objective function can be very different from the original one, the set of its optimal solutions too. Moreover, this objective function is a sum of 2|V| terms; hence, its computation is not immediately polynomial. We give sufficient conditions for large classes of graph-problems under which objective functions of the probabilistic counterparts are polynomially computable and optimal solutions are well-characterized. Finally, we apply these general results to natural and well-known combinatorial problems that belong to the classes considered.en
dc.relation.isversionofjnlnameAlgorithmic Operations Research
dc.relation.isversionofjnlvol15en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages49-64en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherPreeminent Academic Facets Inc.en
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record