A Fast 2-Approximation of Minimum Manhattan Networks

Fuchs, Bernhard and Schulze, Anna (2009) A Fast 2-Approximation of Minimum Manhattan Networks.
Technical Report , 27 p.

Abstract

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 2-approximation for this problem in time O(n log n).


Actions:
Download: [img] PDF
Download (337Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-590
Depositing User: Bernhard Fuchs
Date Deposited: 20 May 2010 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/590