A Simple 3Approximation of Minimum Manhattan Networks
Fuchs, Bernhard and Schulze, Anna
(2008)
A Simple 3Approximation of Minimum Manhattan Networks.
Technical Report
, 16 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 NPhard to construct a minimum Manhattan network. The best approximations published so far are a combinatorial 3approximation algorithm in time O(n log n), and an LPbased 2approximation algorithm. We present a new combinatorial 3approximation for this problem in time O(n log n). Both our algorithm and its analysis are considerably simpler than the prior 3approximation.
Download: 
PDF
Download (246kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  7 (Google Scholar)  
Uncontrolled Keywords:  minimum Manhattan network approximation algorithms rectilinear routing VLSI design 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle 
Related URLs: 
ZAIK Number:  zaik2008570 

Depositing User:  Bernhard Fuchs 
Date Deposited:  11 Dec 2008 00:00 
Last Modified:  19 Dec 2011 09:44 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/570 