Polynomial-time approximation schemes for the Euclidean survivable network design problem
The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimum-cost subgraph satisfying predetermined connectivity requirements. In this paper we consider its geometric version in which the input is a complete Euclidean graph. We assume that each vertex v has been assigned a connectivity requirement r(upsilon).. The output subgraph is supposed
