%0 Journal Article %1 dgkksw-ammnh-Algorithmica15 %A Das, Aparna %A Gansner, Emden R. %A Kaufmann, Michael %A Kobourov, Stephen %A Spoerhase, Joachim %A Wolff, Alexander %D 2015 %J Algorithmica %K approximation_algorithms computational_geometry minimum_Manhattan_networks myown %N 1 %P 36--52 %R 10.1007/s00453-013-9778-z %T Approximating Minimum Manhattan Networks in Higher Dimensions %V 71 %X We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in~$R^d$, find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair's Manhattan (that is, $L_1$-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless $P = NP$). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension~$d$ and any $\epsilon>0$, an $O(n^\epsilon)$-approxi\-ma\-tion algorithm. For 3D, we also give a $4(k-1)$-approximation algorithm for the case that the terminals are contained in the union of $k \ge 2$ parallel planes.

@article{dgkksw-ammnh-Algorithmica15, abstract = {We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called \emph{terminals} in~$\mathbb{R}^d$, find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair's Manhattan (that is, $L_1$-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless ${\cal P} = {\cal NP}$). Approximation algorithms are known for 2D, but not for 3D. \par We present, for any fixed dimension~$d$ and any $\epsilon>0$, an $O(n^\epsilon)$-approxi\-ma\-tion algorithm. For 3D, we also give a $4(k-1)$-approximation algorithm for the case that the terminals are contained in the union of $k \ge 2$ parallel planes.}, added-at = {2024-04-29T21:12:31.000+0200}, author = {Das, Aparna and Gansner, Emden R. and Kaufmann, Michael and Kobourov, Stephen and Spoerhase, Joachim and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2fe30167803295cdc46dae57fb048ef1b/awolff}, doi = {10.1007/s00453-013-9778-z}, interhash = {34e06db0e905eb9ef3b024e80dd9a652}, intrahash = {fe30167803295cdc46dae57fb048ef1b}, journal = {Algorithmica}, keywords = {approximation_algorithms computational_geometry minimum_Manhattan_networks myown}, number = 1, pages = {36--52}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/dgkksw-ammnh-Algorithmica13.pdf}, timestamp = {2024-04-29T21:12:31.000+0200}, title = {Approximating Minimum {Manhattan} Networks in Higher Dimensions}, volume = 71, year = 2015 }