Polylogarithmic Approximation for Generalized Minimum Manhattan Networks

We consider the generalized minimum Manhattan network problem (GMMN). The input to this problem is a set R of n pairs of terminals, which are points in R. The goal is to find a minimum-length rectilinear network that connects every pair in R by a Manhattan path, that is, a path of axis-parallel line segments whose total length equals the pair’s Manhattan distance. This problem is a generalization of the extensively studied minimum Manhattan network problem (MMN) in which R consists of all possible pairs of terminals. Another important special case is the well-known rectilinear Steiner arborescence problem (RSA). As a generalization of these problems, GMMN is NP-hard but approximation algorithms are only known for MMN and RSA. We give the first approximation algorithm for GMMN; our algorithm has a ratio of O(log n) for the problem in arbitrary and fixed dimension d. This is an exponential improvement upon the O(n)-ratio of an existing algorithm for MMN in d dimensions [ESA’11]. For the important case of dimension d = 2, we derive an improved bound of O(log n). Finally, we show that an existing O(log n)-approximation algorithm for two-dimensional RSA generalizes to higher dimensions.