
What about future? Robustness under vertex-uncertainty in graph-problems
Murat, Cécile; Paschos, Vangelis (2006), What about future? Robustness under vertex-uncertainty in graph-problems. https://basepub.dauphine.fr/handle/123456789/20907
View/ Open
Type
Document de travail / Working paperDate
2006Series title
Cahier du LAMSADESeries number
236Published in
Paris
Metadata
Show full item recordAuthor(s)
Murat, CécileLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We study a robustness 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 robust counterparts are polynomially computable and optimal solutions are well-characterized. Finally, we apply these general results to natural and well-known representatives of any of the classes considered.Subjects / Keywords
graph-problemsRelated items
Showing items related by title and author.
-
Murat, Cécile; Paschos, Vangelis (2008) Communication / Conférence
-
Paschos, Vangelis; Murat, Cécile (2010) Article accepté pour publication ou publié
-
Paschos, Vangelis; Murat, Cécile (2002) Article accepté pour publication ou publié
-
Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Gabrel, Virginie; Moulet, Alain; Murat, Cécile; Paschos, Vangelis (1997) Article accepté pour publication ou publié