The minimal Manhattan network problem in three dimensions
X Munoz, S Seibert, W Unger - International Workshop on Algorithms and …, 2009 - Springer
X Munoz, S Seibert, W Unger
International Workshop on Algorithms and Computation, 2009•SpringerAbstract 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 \calNP-and
\calAPX-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 …
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 \calNP-and
\calAPX-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 …
Abstract
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 - and -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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果