The minimum Manhattan network problem approximations and exact solutions

Abstract

A Manhattan p–q path is a geodesic in the Manhattan (or L1-) metric that connects p and q, i.e. a staircase path between p and q. Given a set of points P in the plane, a Manhattan network is a set of axis-parallel line segments that contains a Manhattan p–q path for each pair {p, q} of points in P. In this paper we consider the minimum Manhattan network problem which consists of finding a Manhattan network of minimum total length, an MMN in short, i.e. a 1-spanner for the Manhattan metric. The problem is likely to have applications in VLSI layout. Its complexity status is unknown. The problem has been considered before. Gudmundsson et al. have proposed a factor-8 O(n log n)-time and a factor-4 O(n3)-time approximation algorithm, where n is the number of input points. Later Kato et al. have given a factor-2 O(n3)-time approximation algorithm. However, their correctness proof is incomplete. In this paper we give a geometric factor-3 approximation algorithm that runs in O(n log n) time and the first mixed-integer programming (MIP) formulation for the MMN problem. We have implemented and evaluated both approaches.