Show simple item record

Steiner forests on stochastic metric graphs

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorTelelis, Orestis
dc.contributor.authorZissimopoulos, Vassilis
dc.date.accessioned2011-04-05T12:12:04Z
dc.date.available2011-04-05T12:12:04Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5905
dc.language.isoenen
dc.subjectapproximationen
dc.subjectAlgorithmsen
dc.subjectSteiner forestsen
dc.subjectGraphsen
dc.subject.ddc003en
dc.titleSteiner forests on stochastic metric graphsen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider the problem of connecting given vertex pairs over a stochastic metric graph, each vertex of which has a probability of presence independently of all other vertices. Vertex pairs requiring connection are always present with probability 1. Our objective is to satisfy the connectivity requirements for every possibly materializable subgraph of the given metric graph, so as to optimize the expected total cost of edges used. This is a natural problem model for cost-efficient Steiner Forests on stochastic metric graphs, where uncertain availability of intermediate nodes requires fast adjustments of traffic forwarding. For this problem we allow a priori design decisions to be taken, that can be modified efficiently when an actual subgraph of the input graph materializes. We design a fast (almost linear time in the number of vertices) modification algorithm whose outcome we analyze probabilistically, and show that depending on the a priori decisions this algorithm yields 2 or 4 approximation factors of the optimum expected cost. We also show that our analysis of the algorithm is tight.en
dc.identifier.citationpages112-123en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber4616
dc.relation.ispartoftitleCombinatorial Optimization and Applications First International Conference, COCOA 2007, Xi'an, China, August 14-16, 2007, Proceedingsen
dc.relation.ispartofeditorDress, Andreas
dc.relation.ispartofeditorXu, Yinfeng
dc.relation.ispartofeditorZhu, Binhai
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2007
dc.relation.ispartofpages390en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-540-73556-4en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-73555-7en
dc.relation.conftitleFirst International Conference on Combinatorial Optimization and Applications (COCOA'07)en
dc.relation.confdate2007-08
dc.relation.confcityXi'anen
dc.relation.confcountryChineen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-73556-4_14


Files in this item

Thumbnail
Name:
steiner_forests.PDF
Size:
326.8Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record