Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs *

We survey the area of the design of approximation schemes for geometric variants of the following classical optimization problem: For a given undirected weighted graph, find its minimum-cost subgraph that satisfies a priori given multiconnectivity requirements. We present the approximation schemes for various geometric minimum-cost k-connectivity problems and for geometric survivability problems, giving a detailed tutorial of the novel techniques developed for these algorithms.