Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBoria, Nicolas
HAL ID: 21013
ORCID: 0000-0002-0548-4257
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMurat, Cécile*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2011-11-02T16:03:24Z
dc.date.available2011-11-02T16:03:24Z
dc.date.issued2012
dc.identifier.issn1570-1166
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/7372
dc.language.isoenen
dc.subjectSpanning tree
dc.subjectProbabilistic optimization
dc.subjectComplexity
dc.subjectApproximation
dc.subject.ddc003en
dc.titleOn the probabilistic min spanning tree Problem
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.
dc.relation.isversionofjnlnameJournal of Mathematical Modelling and Algorithms
dc.relation.isversionofjnlvol11
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages45-76
dc.relation.isversionofdoi10.1007/s10852-011-9165-1
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherKluwer Academic Publishers
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-21T08:20:04Z
hal.identifierhal-01495334*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record