Minimum Mannhattan Networks

Approximations for the Minimum Manhattan network problem

Given a set of n points in the plane, a Manhattan network is the union of vertical and horizontal line segments. such that each pair of points is connected by a shortest rectilinear staircase path, a Manhattan path. We call a network a minimum Manhattan network if the total length of its segments is minimum among all Manhattan networks. The complexity status of the problem is still unknown.

We established a factor-3 approximation algorithm that runs in O(n log n) time. On the left hand you see an example of a minimum Manhattan network, its length is 36. On the right hand you see the Manhattan network computed by our algorithm is depicted, its length is 41. You can test the algorithm here . Furthermore, we implemented a mixed integer program to solve the problem optimally in order to measure the practical results of our algorithm. The results of our practical evaluation can be seen in [1]. It turned out that our algorithm performs better in practice than the theoretic factor of 3 suggests. On average our Manhattan networks were only 1.3 times longer than the corresponding minimum ones.

In the meantime a group of French researchers managed to come up with a factor-2 approximation algorithm. Their algorithm is based on a technique that rounds the solution variables of the relaxed mixed inter program.

Joint work with Takeshi Shirabe and Florian Widmann.

Publications

  1. Marc Benkert, Alexander Wolff, Florian Widmann, and Takeshi Shirabe. The minimum Manhattan network problem: Approximations and exact solutions. Computational Geometry: Theory and Applications, 35(3):188-208, 2006. [ bib | html | pdf | abstract ]
  2. Marc Benkert, Florian Widmann, and Alexander Wolff. The minimum Manhattan network problem: A fast factor-3 approximation. In Jin Akiyama, Mikio Kano, and Xuehou Tan, editors, Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04), volume 3742 of Lecture Notes in Computer Science, pages 16-28. Springer-Verlag, 2005. [ bib | html | pdf ]
  3. Marc Benkert, Florian Widmann, and Alexander Wolff. The minimum Manhattan network problem: A fast factor-3 approximation. Technical Report 2004-16, Fakultät für Informatik, Universität Karlsruhe, 2004. Available at http://digbib.ubka.uni-karlsruhe.de/volltexte/1000003164. [ bib | html | pdf ]
  4. Alexander Wolff, Marc Benkert, and Takeshi Shirabe. The minimum Manhattan network problem: Approximations and exact solutions. In Proc. 20th European Workshop on Computational Geometry (EWCG'04), pages 209-212, Sevilla, 2004. [ bib | pdf ]