2012/03/29 by Aparna Das, Das, Aparna, Krzysztof Fleszar +9
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1203.6481
published as Algorithmica 80, pages 1170-1190, 2018 · 14 pages, 5 figures; added appendix and figures
arxiv created 2012/04/23 · arxiv updated 2026/08/03
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 ≥ 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(logd+1 n)-approximation algorithm for GMMN (and, hence, MMN) in d ≥ 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.