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(
nlog
n), 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.
References secured to subscribers.