Show simple item record

dc.contributor.authorMurat, Cécile
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-03-22T09:32:42Z
dc.date.available2011-03-22T09:32:42Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5781
dc.descriptionLa version document de travail est intitulée "What about future? Robustness under vertex-uncertainty in graph-problems"en
dc.language.isoenen
dc.subjectGraphsen
dc.subject.ddc003en
dc.titleVertex-uncertainty in graph-problemsen
dc.typeCommunication / Conférence
dc.description.abstractenWe study a probabilistic model for graph-problems under vertex-uncertainty. We assume that any vertex v i of the input-graph G has only a probability p i 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, where V is the vertex-set of G; 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.en
dc.identifier.citationpages139-148en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber5165
dc.relation.ispartoftitleCombinatorial Optimization and Applications Second International Conference, COCOA 2008, St. John's, NL, Canada, August 21-24, 2008, Proceedingsen
dc.relation.ispartofeditorYang, Boting
dc.relation.ispartofeditorDu, Ding-Zhu
dc.relation.ispartofeditorWang, Cao An
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2008
dc.relation.ispartofpages480en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-540-85097-7en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-85096-0en
dc.relation.conftitleSecond International Conference on Combinatorial Optimization and Applications (COCOA'08)en
dc.relation.confdate2008-08
dc.relation.confcitySt John'sen
dc.relation.confcountryCanadaen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-85097-7_13


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record