
On the probabilistic min spanning tree Problem
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012), On the probabilistic min spanning tree Problem, Journal of Mathematical Modelling and Algorithms, 11, 1, p. 45-76. 10.1007/s10852-011-9165-1
Voir/Ouvrir
Type
Article accepté pour publication ou publiéDate
2012Nom de la revue
Journal of Mathematical Modelling and AlgorithmsVolume
11Numéro
1Éditeur
Kluwer Academic Publishers
Pages
45-76
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Boria, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Murat, Cécile
Laboratoire 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]
Résumé (EN)
We study a probabilistic optimization model for min spanning tree, where any vertex v i of the input-graph G(V, E) has some presence probability p i in the final instance G′ ⊂ G that will effectively be optimized. Suppose that when this “real” instance G′ becomes known, a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G′. The goal is to compute an anticipatory spanning tree of G such that, its modification for any GG is optimal for G′. This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.Mots-clés
Spanning tree; Probabilistic optimization; Complexity; ApproximationPublications associées
Affichage des éléments liés par titre et auteur.
-
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2011) Communication / Conférence
-
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2018) Article accepté pour publication ou publié
-
Boria, Nicolas; Paschos, Vangelis (2010) Article accepté pour publication ou publié
-
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2012) Document de travail / Working paper
-
Murat, Cécile; Paschos, Vangelis (2002) Article accepté pour publication ou publié