### Abstract

Original language | English |
---|---|

Pages (from-to) | 561-572 |

Number of pages | 12 |

Journal | Mathematics of Operations Research |

Volume | 39 |

Issue number | 2 |

Early online date | 6 Sep 2013 |

DOIs | |

State | Published - 2014 |

### Cite this

*Mathematics of Operations Research*,

*39*(2), 561-572. DOI: 10.1287/moor.2013.0620

}

*Mathematics of Operations Research*, vol 39, no. 2, pp. 561-572. DOI: 10.1287/moor.2013.0620

**Approximability of Robust Network Design.** / Olver, N.K.; Shepherd, F.B.

Research output: Scientific - peer-review › Article

TY - JOUR

T1 - Approximability of Robust Network Design

AU - Olver,N.K.

AU - Shepherd,F.B.

PY - 2014

Y1 - 2014

N2 - We consider robust (undirected) network design (RND) problems where the set of feasible demands may be given by an arbitrary convex body. This model, introduced by Ben-Ameur and Kerivin [Ben-Ameur W, Kerivin H (2003) New economical virtual private networks. Comm. ACM 46(6):69-73], generalizes the well-studied virtual private network (VPN) problem. Most research in this area has focused on constant factor approximations for specific polytope of demands, such as the class of hose matrices used in the definition of VPN. As pointed out in Chekuri [Chekuri C (2007) Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News 38(3):106-128], however, the general problem was only known to be APX-hard (based on a reduction from the Steiner tree problem). We show that the general robust design is hard to approximate to within polylogarithmic factors. We establish this by showing a general reduction of buy-at-bulk network design to the robust network design problem. Gupta pointed out that metric embeddings imply an O4log n5-approximation for the general RND problem, and hence this is tight up to polylogarithmic factors. In the second part of the paper, we introduce a natural generalization of the VPN problem. In this model, the set of feasible demands is determined by a tree with edge capacities; a demand matrix is feasible if it can be routed on the tree. We give a constant factor approximation algorithm for this problem that achieves factor of 8 in general, and 2 for the case where the tree has unit capacities. As an application of this result, we consider so-called H-tope demand polytopes. These correspond to demands which are routable in some graph H. We show that the corresponding RND problem has an O415-approximation if H admits a stochastic constant-distortion embedding into tree metrics. © 2014 INFORMS.

AB - We consider robust (undirected) network design (RND) problems where the set of feasible demands may be given by an arbitrary convex body. This model, introduced by Ben-Ameur and Kerivin [Ben-Ameur W, Kerivin H (2003) New economical virtual private networks. Comm. ACM 46(6):69-73], generalizes the well-studied virtual private network (VPN) problem. Most research in this area has focused on constant factor approximations for specific polytope of demands, such as the class of hose matrices used in the definition of VPN. As pointed out in Chekuri [Chekuri C (2007) Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News 38(3):106-128], however, the general problem was only known to be APX-hard (based on a reduction from the Steiner tree problem). We show that the general robust design is hard to approximate to within polylogarithmic factors. We establish this by showing a general reduction of buy-at-bulk network design to the robust network design problem. Gupta pointed out that metric embeddings imply an O4log n5-approximation for the general RND problem, and hence this is tight up to polylogarithmic factors. In the second part of the paper, we introduce a natural generalization of the VPN problem. In this model, the set of feasible demands is determined by a tree with edge capacities; a demand matrix is feasible if it can be routed on the tree. We give a constant factor approximation algorithm for this problem that achieves factor of 8 in general, and 2 for the case where the tree has unit capacities. As an application of this result, we consider so-called H-tope demand polytopes. These correspond to demands which are routable in some graph H. We show that the corresponding RND problem has an O415-approximation if H admits a stochastic constant-distortion embedding into tree metrics. © 2014 INFORMS.

U2 - 10.1287/moor.2013.0620

DO - 10.1287/moor.2013.0620

M3 - Article

VL - 39

SP - 561

EP - 572

JO - Mathematics of Operations Research

T2 - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 2

ER -