A Simple 3-Approximation of Minimum Manhattan Networks

Fuchs, Bernhard and Schulze, Anna (2008) A Simple 3-Approximation of Minimum Manhattan Networks.
Technical Report , 16 p.


Given a set P of n points in the plane, a Manhattan network of P is a network that contains a rectilinear shortest path between every pair of points of P. A minimum Manhattan network of P is a Manhattan network of minimum total length. It is unknown whether it is NP-hard to construct a minimum Manhattan network. The best approximations published so far are a combinatorial 3-approximation algorithm in time O(n log n), and an LP-based 2-approximation algorithm. We present a new combinatorial 3-approximation for this problem in time O(n log n). Both our algorithm and its analysis are considerably simpler than the prior 3-approximation.

Download: [img] PDF
Download (246kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2008-570
Depositing User: Bernhard Fuchs
Date Deposited: 11 Dec 2008 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/570