Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorTelelis, Orestis
dc.contributor.authorZissimopoulos, Vassilis
dc.date.accessioned2010-03-16T08:58:51Z
dc.date.available2010-03-16T08:58:51Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3700
dc.language.isoenen
dc.subjectComplexityen
dc.subjectGraphen
dc.subjectApproximationen
dc.subjectForesten
dc.subjectSteiner Treeen
dc.subject.ddc003en
dc.titleProbabilistic models for the Steiner Tree problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider a probabilistic model for the Steiner Tree problem. Under this model, the problem is defined in a two-stage setting over a first-stage complete weighted graph having its vertices associated with a probability of presence (independently each from another) in the second stage. A first-stage feasible solution on the input graph might become infeasible in the second stage, when certain vertices of the graph fail. Therefore, a well defined modification strategy is devised for modifying the remainders of a first-stage solution to render it second-stage feasible. The objective is to minimize the expected weight of the second-stage solution over the distribution of all possible second-stage materializable subgraphs of the input graph. We recognize two complementary computational problems in this setting, one being the a priori computation of first-stage decisions given a particular modification strategy, and the second being the cost-efficient modification of a first-stage feasible solution. We prove that both these problems are NP-hard for the Steiner Tree problem under this setting. We design and analyze probabilistically an efficient modification strategy and derive tight approximation results for both aforementioned problems. We show that our techniques can be extended to the case of the more general Steiner Forest problem in the same probabilistic setting.en
dc.relation.isversionofjnlnameNetworks
dc.relation.isversionofjnlvol56
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages39-49
dc.relation.isversionofdoihttp://dx.doi.org/10.1002/net.20346en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherWileyen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record