Approximability of Robust Network Design

N.K. Olver, F.B. Shepherd

Abstract

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.
Original languageEnglish
Pages (from-to)561-572
Number of pages12
JournalMathematics of Operations Research
Volume39
Issue number2
Early online date6 Sep 2013
DOIs
StatePublished - 2014

Cite this

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

In: Mathematics of Operations Research, Vol. 39, No. 2, 2014, p. 561-572.

Research output: Scientific - peer-reviewArticle

@article{a10722bbc7ec482cae9c3d14f6c837fe,
title = "Approximability of Robust Network Design",
abstract = "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.",
author = "N.K. Olver and F.B. Shepherd",
year = "2014",
doi = "10.1287/moor.2013.0620",
volume = "39",
pages = "561--572",
journal = "Mathematics of Operations Research",
issn = "0364-765X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "2",

}

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

In: Mathematics of Operations Research, Vol. 39, No. 2, 2014, p. 561-572.

Research output: Scientific - peer-reviewArticle

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 -