A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem

Zeyu Guo, He Sun, Hong Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Given a set T of n points in ℝ2, a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p,q ∈ T, in G there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between p and q. The Minimum Manhattan Network (MMN) problem is to find a Manhattan network of the minimum length, i.e., the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity O(2), which improves the 2-approximation algorithm with time complexity Ω(n 8), proposed by Chepoi, Nouioua et al.. To the best of our knowledge, this is the best result on this problem.
Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings
Pages212-223
Number of pages12
ISBN (Electronic)978-3-540-68880-8
DOIs
Publication statusPublished - 2008
Event4th International Conference on Algorithmic Aspects in Information and Management - Shanghai, China
Duration: 23 Jun 200825 Jun 2008

Conference

Conference4th International Conference on Algorithmic Aspects in Information and Management
Abbreviated titleAAIM 2008
Country/TerritoryChina
CityShanghai
Period23/06/0825/06/08

Fingerprint

Dive into the research topics of 'A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem'. Together they form a unique fingerprint.

Cite this