Lena Strobl:
Algorithms for Minimum Manhattan Networks
Kurzbeschreibung
For a given set of points in the plane V we call a graph G = (V ∪ S, E) with Steiner points S a Manhattan network if it only includes axis-parallel edges and connects each pair of vertices via a path of minimal distance. Finding minimum L1-norm Manhattan networks for given input points V is a problem introduced and first studied by Gudmundsson, Levcopoulos and Narasimhan. Finding minimum L1 Manhattan networks is known to be an NP-hard problem. We present an algorithm constructing a 4-approximation for the length minimization problem in O(n³). We also consider the problem of minimizing the amount of introduced Steiner points |S| and present an algorithm giving us a 2-approximation in O(n³).