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

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

0.00 Avg rating0 Votes
Article ID: iaor20031584
Country: Netherlands
Volume: 30
Issue: 4
Start Page Number: 265
End Page Number: 268
Publication Date: Aug 2002
Journal: Operations Research Letters
Authors: ,
Abstract:

Given a graph G = (V,E) with edge costs and an integer vector r∈ℤ+V 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 r∈{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.

Reviews

Required fields are marked *. Your email address will not be published.