Strong inequalities for capacitated survivable network design problems

Abstract.

We present several classes of facet-defining inequalities to strengthen polyhedra arising as subsystems of network design problems with survivability constraints. These problems typically involve assigning capacities to a network with multicommodity demands, such that after a vertex- or edge-deletion at least some prescribed fraction of each demand can be routed.

Similar content being viewed by others

Fast Exact Algorithms for Survivable Network Design with Uniform Requirements

Article 20 May 2022

Improved Approximations for Relative Survivable Network Design

Chapter © 2023

Approximation Algorithms for Multi-budgeted Network Design Problems

Chapter © 2015

Author information

Authors and Affiliations

1. Columbia University, New York, NY 10027, , , , , , US

   Daniel Bienstock & Gabriella Muratore

Authors

1. Daniel Bienstock
   View author publications

   You can also search for this author in PubMed Google Scholar

2. Gabriella Muratore
   View author publications

   You can also search for this author in PubMed Google Scholar

Additional information

Received: December 1997 / Accepted: April 2000¶Published online September 20, 2000

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bienstock, D., Muratore, G. Strong inequalities for capacitated survivable network design problems. Math. Program. 89, 127–147 (2000). https://doi.org/10.1007/PL00011390

Download citation

• Issue Date: November 2000

• DOI: https://doi.org/10.1007/PL00011390

• Mathematics Subject Classification (1991): 90C11, 68M10