A rounding algorithm for approximating minimum Manhattan networks

For a set T of n points (terminals) in the plane, a Manhattan 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 superset of T and for every pair of terminals, the network N(T) contains a shortest l(1)-path between them. A minimum Manhattan network on T is a Manhattan network of minimum possible length. The problem of finding minimum Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan [J. Gudmundsson, C. Levcopoulos, G. Narasimhan, Approximating a minimum Manhattan network, Nordic Journal of Computing 8 (2001) 219-232. Proc. APPROX'99, 1999, pp. 28-37] and its complexity status is unknown. Several approximation algorithms (with factors 8, 4, and 3) have been proposed; recently Kato, Imai, and Asano [R. Kato, K. Imai, T. Asano, An improved algorithm for the minimum Manhattan network problem, ISAAC'02, in: LNCS, vol. 2518, 2002, pp. 344-356] have given a factor 2-approximation algorithm, however their correctness proof is incomplete. In this paper, we propose a rounding 2-approximation algorithm based on an LP-formulation of the minimum Manhattan network problem. (C) 2007 Elsevier B.V. All rights reserved.