Abstract

In this paper we address the Minimum Manhattan Network (MMN) problem. It is an important geometric problem with vast applications. As it is an NP-complete discrete combinatorial optimization problem we employ a simple metaheuristic namely Simulated Annealing. We have also developed benchmark datasets and tested our algorithm with the dataset.

References

• Marc Benkert, Alexander Wolff, and Florian Widmann. The minimum manhattan network problem: A fast factor-3 approximation. In Proceedings of the 2004 Japanese Conference on Discrete and Computational Geometry, JCDCG'04, pages 16–28, Berlin, Heidelberg, 2005. Springer-Verlag.
• Marc Benkert, Alexander Wolff, Florian Widmann, and Takeshi Shirabe. The minimum manhattan network problem: Approximations and exact solutions. Comput. Geom. Theory Appl. , 35(3):188–208, October 2006.
• Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. , 35(3):268–308, September 2003.
• Victor Chepoi, Karim Nouioua, and Yann Vax`es. A rounding algorithm for approximating minimum manhattan networks. Theor. Comput. Sci. , 390(1):56–69, January 2008.
• Francis Y. L. Chin, Zeyu Guo, and He Sun. Minimum manhattan network is np-complete. In Proceedings of the Twentyfifth Annual Symposium on Computational Geometry, SCG '09, pages 393–402, New York, NY, USA, 2009. ACM.
• Aparna Das, Krzysztof Fleszar, Stephen G. Kobourov, Joachim Spoerhase, Sankar Veeramoni, and AlexanderWolff. Polylogarithmic approximation for generalized minimum manhattan networks. CoRR, 2012.
• V. ern. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1):41–51, 1985.
• Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. Approximating a minimum manhattan network. Nordic J. of Computing, 8(2):219–232, June 2001.
• Zeyu Guo, He Sun, and Hong Zhu. A fast 2-approximation algorithm for the minimum manhattan network problem. In Rudolf Fleischer and Jinhui Xu, editors, Algorithmic Aspects in Information and Management, volume 5034 of Lecture Notes in Computer Science, pages 212–223. Springer Berlin Heidelberg, 2008.
• Zeyu Guo, He Sun, and Hong Zhu. Greedy construction of 2- approximation minimum manhattan network. In Proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC '08, pages 4–15, Berlin, Heidelberg, 2008. Springer-Verlag.
• Ryo Kato, Keiko Imai, and Takao Asano. An improved algorithm for the minimum manhattan network problem. In Proceedings of the 13th International Symposium on Algorithms and Computation, ISAAC '02, pages 344–356, London, UK, UK, 2002. Springer-Verlag.
• S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. SCIENCE, 220(4598):671–680, 1983.
• Xavier Muoz, Sebastian Seibert, and Walter Unger. The minimal manhattan network problem in three dimensions. In Sandip Das and Ryuhei Uehara, editors, WALCOM: Algorithms and Computation, volume 5431 of Lecture Notes in Computer Science, pages 369–380. Springer Berlin Heidelberg, 2009.
• Lior Pachter and Fumei Lam. Picking alignments from (steiner) trees. In Proceedings of the Sixth Annual International Conference on Computational Biology, RECOMB '02, pages 246–253, New York, NY, USA, 2002. ACM.
• Sebastian Seibert and Walter Unger. A 1. 5-approximation of the minimal manhattan network problem. In Proceedings ofthe 16th International Conference on Algorithms and Computation, ISAAC'05, pages 246–255, Berlin, Heidelberg, 2005. Springer-Verlag.