Polylogarithmic Approximation for Generalized Minimum Manhattan Networks

Details Polylogarithmic Approximation for Generalized Minimum Manhattan Networks Polylogarithmic Approximation for Generalized Minimum Manhattan Networks

2012-03-29

arxiv.org/abs/1203.6481v2

Computer Science

Computational Geometry

14 pages, 5 figures; added appendix and figures

Scientific paper

Given a set of $n$ terminals, which are points in $d$-dimensional Euclidean space, the minimum Manhattan network problem (MMN) asks for a minimum-length rectilinear network that connects each pair of terminals by a Manhattan path, that is, a path consisting of axis-parallel segments whose total length equals the pair's Manhattan distance. Even for $d=2$, the problem is NP-hard, but constant-factor approximations are known. For $d \ge 3$, the problem is APX-hard; it is known to admit, for any $\eps > 0$, an $O(n^\eps)$-approximation. In the generalized minimum Manhattan network problem (GMMN), we are given a set $R$ of $n$ terminal pairs, and the goal is to find a minimum-length rectilinear network such that each pair in $R$ is connected by a Manhattan path. GMMN is a generalization of both MMN and the well-known rectilinear Steiner arborescence problem (RSA). So far, only special cases of GMMN have been considered. We present an $O(\log^{d+1} n)$-approximation algorithm for GMMN (and, hence, MMN) in $d \ge 2$ dimensions and an $O(\log n)$-approximation algorithm for 2D. We show that an existing $O(\log n)$-approximation algorithm for RSA in 2D generalizes easily to $d>2$ dimensions.

Affiliated with

Also associated with

No associations

Rating

Polylogarithmic Approximation for Generalized Minimum Manhattan Networks 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 Polylogarithmic Approximation for Generalized Minimum Manhattan Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polylogarithmic Approximation for Generalized Minimum Manhattan Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57547