%0 Journal Article %1 dfksvw-agmmnp-Algorithmica18 %A Das, Aparna %A Fleszar, Krzysztof %A Kobourov, Stephen G. %A Spoerhase, Joachim %A Veeramoni, Sankar %A Wolff, Alexander %D 2018 %J Algorithmica %K Approximation_Algorithms Computational_Geometry Minimum_Manhattan_Network myown %N 4 %P 1170--1190 %R 10.1007/s00453-017-0298-0 %T Approximating the Generalized Minimum Manhattan Network Problem %V 80 %X 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 $R^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(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(łog^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^\epsilon)$-ratio for MMN in $d$ dimensions ESA 2011. En route, we show that an existing $O(n)$-approximation algorithm for 2D-RSA generalizes to higher dimensions.

@article{dfksvw-agmmnp-Algorithmica18, abstract = {We consider the \emph{generalized minimum Manhattan network problem} (GMMN). The input to this problem is a set $R$ of $n$ pairs of terminals, which are points in $\mathbb{R}^2$. The goal is to find a minimum-length rectilinear network that connects every pair in $R$ by a \emph{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 \emph{minimum Manhattan network problem} (MMN) in which $R$ consists of all possible pairs of terminals. Another important special case is the well-known \emph{rectilinear Steiner arborescence problem} (RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. \par 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^\epsilon)$-ratio for MMN in $d$ dimensions [ESA 2011]. En route, we show that an existing $O(\log n)$-approximation algorithm for 2D-RSA generalizes to higher dimensions.}, added-at = {2024-02-18T09:53:56.000+0100}, author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/21fb375f957c329c7b02903eb4c526dc0/awolff}, doi = {10.1007/s00453-017-0298-0}, interhash = {0f4e49be96efd60af144232c3cf97bc6}, intrahash = {1fb375f957c329c7b02903eb4c526dc0}, journal = {Algorithmica}, keywords = {Approximation_Algorithms Computational_Geometry Minimum_Manhattan_Network myown}, number = 4, pages = {1170--1190}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/dfksvw-agmmnp-Algorithmica18.pdf}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/dfksvw-agmmnp-ISAAC13-slides.pdf}, timestamp = {2024-04-27T23:03:22.000+0200}, title = {Approximating the Generalized Minimum {Manhattan} Network Problem}, volume = 80, year = 2018 }