Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm

Details Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm

2010-04-30

arxiv.org/abs/1004.5517v2

Computer Science

Computational Geometry

16 pages, 5 figures; corrected typos, reference added, figure added

Scientific paper

Let B be a centrally symmetric convex polygon of R^2 and || p - q || be the distance between two points p,q in R^2 in the normed plane whose unit ball is B. For a set T of n points (terminals) in R^2, a B-Manhattan network on T is a network N(T) = (V,E) with the property that its edges are parallel to the directions of B and for every pair of terminals t_i and t_j, the network N(T) contains a shortest B-path between them, i.e., a path of length || t_i - t_j ||. A minimum B-Manhattan network on T is a B-Manhattan network of minimum possible length. The problem of finding minimum B-Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) in the case when the unit ball B is a square (and hence the distance || p - q || is the l_1 or the l_infty-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (SoCG'09) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4 ,3 , and 2) for minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for minimum B-Manhattan network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (APPROX'05) and subsequently used in other factor 2 approximation algorithms for minimum Manhattan problem.

Affiliated with

Also associated with

No associations

Rating

Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-387999