Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Greedy Construction of 2-Approximation Minimum Manhattan Network

Zeyu Guo4, He Sun4 and Hong Zhu5

(4)  Fudan University, China
(5)  East China Normal University, China
Abstract
Given a set T of n points in , 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 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(nlogn), which improves the 2-approximation algorithm with time complexity O(n2). Moreover, compared with other 2-approximation algorithms employing linear programming or dynamic programming technique, it was first discovered that only greedy strategy suffices to get 2-approximation network.

Keywords  Minimum Manhattan Network - approximation algorithm - greedy strategy

This work is supported by Shanghai Leading Academic Discipline Project(Project Number:B412), National Natural Science Fund (grant #60496321), and the ChunTsung Undergraduate Research Endowment.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)