Show simple item record

dc.contributor.authorBoria, Nicolas
HAL ID: 21013
ORCID: 0000-0002-0548-4257
dc.contributor.authorMurat, Cécile
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-05-19T13:15:19Z
dc.date.available2011-05-19T13:15:19Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6306
dc.language.isoenen
dc.subjectmin spanning treeen
dc.subjectprobabilistic optimization modelen
dc.subject.ddc003en
dc.titleOn the probabilistic min spanning tree problemen
dc.typeCommunication / Conférence
dc.description.abstractenWe study a probabilistic optimization model for MIN SPANNING TREE, where any vertex vi of the input-graph G(V,E) has some presence probability pi in the final instance G' ⊂ G that will effectively be optimized. Supposing that when this “real” instance G' becomes known, a decision maker might have no time to perform computation from scratch, we assume that a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and, also, that a decision maker can run a quick algorithm, 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 G' ⊆ G 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 as well as of two natural subproblems of it, 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.en
dc.identifier.citationpages893-900en
dc.relation.ispartoftitleProceedings of the 2010 International Multiconference on Computer Science and Information Technology (IMCSIT)en
dc.relation.ispartofpublnameIEEEen
dc.relation.ispartofdate2010
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-4244-6432-6en
dc.relation.conftitleInternational Multiconference on Computer Science and Information Technology (IMCSIT 2010)en
dc.relation.confdate2010-10
dc.relation.confcityWislaen
dc.relation.confcountryPologneen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record