Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
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

Edit
The Minimal Manhattan Network Problem in Three Dimensions   (Citations: 2)
BibTex | RIS | RefWorks Download
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
Cumulative Annual
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 »
    • ...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...

    Francis Y. L. Chin, et al. Minimum Manhattan Network is NP-Complete

Sort by:

Citations (2)

Share this on