Approximating the Generalized Minimum Manhattan Network Problem

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 ℝ

2

. 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 natural 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. No approximation algorithms are known for general GMMN. We obtain an

O

(log

n

)-approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple

O

(log

d

 + 1

n

)-approximation algorithm for the problem in arbitrary fixed dimension

d

. As a corollary, we obtain an exponential improvement upon the previously best

O

(

n

ε

)-ratio for MMN in

d

dimensions [ESA’11]. En route, we show that an existing

O

(log

n

)-approximation algorithm for 2D-RSA generalizes to higher dimensions.