A Rounding Algorithm for Approximating Minimum Manhattan Networks (Extended Abstract)
Victor D. Chepoi, Karim Nouioua, Yann Vaxès · 2005
For a set T of n points (terminals) in the plane, a Man- hattan network on T is a network N (T )=( V,E) with the property that its edges are horizontal or vertical segments connecting points in V ⊇ T and for every pair of terminals, the network N (T )c ontains a shortest l1-path between them. A minimum Manhattan network on T is a Manhattan network of minimum possible length. The problem of find- ing minimum Manhattan networks has been introduced by Gudmunds- son, Levcopoulos, and Narasimhan (APPROX'99) and it is not known whether this problem is in P or not. Several approximation algorithms (with factors 8,4, and 3) have been proposed; recently Kato, Imai, and Asano (ISAAC'02) have given a factor 2 approximation algorithm, how- ever their correctness proof is incomplete. In this note, we propose a rounding 2-approximation algorithm based on a LP-formulation of the minimum Manhattan network problem.