ABSTRACT
We survey approximation algorithms and hardness of approximation results for the Survivable Network problem in which we seek a low edge-cost directed/undirected subgraph that satisfies prescribed connectivity demands w.r.t. a given “connectivity measure.” These problems include the following well-known problems: Minimum Spanning Tree, Traveling Salesman Problem, Steiner Tree, Steiner Forest, and their directed variants. These are examples of low connectivity Survivable Network problems. In this survey, we will consider high-connectivity Survivable Network problems; some examples are Min-Cost k-Flow, k-Inconnected Subgraph, k-Connected Subgraph, and Rooted Survivable Network. See previous surveys on such problem in References 1 and 2.
