[+] PTAS for planar subset-connectivity problems I: construction of a mortar graph-brick decomposition and spanner for subset TSP and Steiner tree
In this lecture we study the breakthrough result of Borradaile, Klein,
and Mathieu regarding a PTAS for Steiner tree in planar
graphs. Steiner tree is a subset-type problem, where we mainly care
about a given subset of terminals in the graph. In particular, the
weight of a Steiner tree can be arbitrarily smaller than the minimum
spanning tree of the graph. This makes it very different from all
problems we have studied so far.
In the previous lecture we got acquainted with Klein's framework for designing PTASes in planar graphs and applied it to the TSP problem. In this lecture, we review this framework and see how to apply it to the Steiner tree problem. We will see that the most difficult step is to obtain a spanner. We study the so called mortar graph-brick decomposition and how it gives rise to a spanner. This decomposition has been applied to further problems as well and has been generalized to bounded-genus graphs.
In Lecture 16 we will describe the algorithm and its correctness based on a structure theorem. The structure theorem itself is presented in Lecture 17.
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 codec. The lecture notes and slides should advance automatically. If you have any trouble with playback, email Erik.