Show simple item record

Separation of partition inequalities for the (1,2)-survivable network design problem

dc.contributor.authorKerivin, Hervé
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-12T08:31:07Z
dc.date.available2010-04-12T08:31:07Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3917
dc.language.isoenen
dc.subjectSeparation algorithmen
dc.subjectSubmodular functionen
dc.subjectPartition inequalitiesen
dc.subjectSurvivable networken
dc.subject.ddc003en
dc.titleSeparation of partition inequalities for the (1,2)-survivable network design problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a graph G=(V,E) with edge costs and an integer vector Image associated with the nodes of V, the survivable network design problem is to find a minimum cost subgraph of G such that between every pair of nodes s,t of V, there are at least min{r(s),r(t)} edge-disjoint paths. In this paper we consider that problem when rset membership, variant{1,2}V. This case is of particular interest to the telecommunication industry. We show that the separation problem for the so-called partition inequalities reduces to minimizing a submodular function. This yields a polynomial time separation algorithm for these inequalities in that case.en
dc.relation.isversionofjnlnameOperations Research Letters
dc.relation.isversionofjnlvol30en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2002-08
dc.relation.isversionofjnlpages265-268en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0167-6377(02)00182-7en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record