We present a framework for designing polynomial-time approximation schemes for network design problems such as Steiner tree and 2-edge connectivity in planar graphs. For a fixed epsilon, a polynomial-time approximation scheme finds, in polynomial time, a solution whose value is within 1+epsilon of the optimal solution.
In this talk I will overview the framework and discuss how to use it to solve a variety of connectivity problems.
Joint work with Claire Mathieu and Philip Klein.