## Keywords (5)

Publications
The Minimal Manhattan Network Problem in Three Dimensions

# The Minimal Manhattan Network Problem in Three Dimensions,10.1007/978-3-642-00202-1_32,Xavier Muñoz,Sebastian Seibert,Walter Unger

The Minimal Manhattan Network Problem in Three Dimensions
For the Minimal Manhattan Network Problem in three dimensions (MMN3D), one is given a set of points in space, and an admissible solution is an axis-parallel network that connects every pair of points by a shortest path under L 1-norm (Manhattan metric). The goal is to minimize the overall length of the network. Here, we show that MMN3D is NP\cal NP- and APX\cal APX-hard, with a lower bound on the approximability of 1 + 2·10− 5. This lower bound applies to MMN2-3D already, a sub-problem in between the two and three dimensional case. For MMN2-3D, we also develop a 3-approximation algorithm which is the first algorithm for the Minimal Manhattan Network Problem in three dimensions at all.
Conference: Workshop on Algorithms and Computation - WALCOM , pp. 369-380, 2009
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
More »

## Citation Context (1)

• ...Muñoz et al. [9 ]g ave anNP-hardness proof of this problem in three dimensions and showed that there is no polynomial-time approximation algorithm with a ratio better than 1 + 2 · 10 −5 under the assumption P �= NP...
• ...Muñoz et al. [9] gave an in-approximation factor in three dimensions...
• ...However, both our reduction presented in this paper and the NPcompleteness proof of the MMN problem in three dimensions [9] cannot be applied directly to obtain an in-approximation ratio of the MMN problem in two dimensions...
• ...and edges. Muñoz et al. [9] generalized the notion of critical rectangles and gave the definition of critical cuboids...

Sort by:

## Citations (2)

### Minimum Manhattan Network is NP-Complete

Journal: Discrete & Computational Geometry - DCG , vol. 45, no. 4, pp. 701-722, 2011

### A Fast 2Approximation of Minimum Manhattan Networks

Published in 2010.