World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.
Happy Thanksgiving! Enjoy 35% OFF minimum 2| Quote GIVETHANKS35 upon checkout, valid till 26 NOV 2021

System Upgrade on Mon, Jun 21st, 2021 at 1am (EDT)

During this period, the E-commerce and registration of new users may not be available for up to 6 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue: Selected Papers from the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008), 15–17 December 2008, Gold Coast, AustraliaNo Access

GREEDY CONSTRUCTION OF 2-APPROXIMATE MINIMUM MANHATTAN NETWORKS

    Given a set T of n points in ℝ2, a Manhattan network on T is a graph G = (V,E) with the property that all the edges in E are vertical or horizontal line segments connecting points in V ⊇ T and for all p, q ∈ T, the graph contains a path having the length exactly L1 distance between p and q. The Minimum Manhattan Network problem is to find a Manhattan network of minimum length, i.e. minimizing the total length of the line segments of the network. In this paper we present a 2-approximation algorithm with time complexity O(n log n), which improves over a recent combinatorial 2-approximation algorithm with running time O(n2). Moreover, compared with other 2-approximation algorithms using linear programming or dynamic programming techniques, we show that a greedy strategy suffices to obtain a 2-approximation algorithm.

    References

    • M. Benkert, T. Shirabe and A. Wolff, The minimum Manhattan network problem: A fast factor-3 approximation, Proc. 20th European Workshop on Computational Geometry pp. 209–212. Google Scholar
    • M. Benkertet al., Comput. Geom.: Th. Appl. 35, 188 (2006). Crossref, ISIGoogle Scholar
    • G. Chalmet, L. Francis and A. Kolen, Eur. J. Oper. Res. 6, 117 (1981), DOI: 10.1016/0377-2217(81)90197-1. Crossref, ISIGoogle Scholar
    • V. Chepoi, K. Nouioua and Y. Vaxès, A rounding algorithm for approximating minimum Manhattan networks, Theor. Comput. Sci. 390 (2008) 56–69. Preliminary version appeared in Proc. 8th Int. Workshop on Approximation Algorithms for Combinatorial Optimization, (2005), pp. 40–51 . Google Scholar
    • F. Y. L. Chin, Z. Guo and H. Sun, Minimum Manhattan network is NP-complete, Proc. 25th Ann. ACM Symp. Computational Geometry pp. 393–402. Google Scholar
    • D. Eppstein, Spanning Trees and Spanners, eds. J. Sack and J. Urrutia (Elsevier Science Publishers B. V. North-Holland, Amsterdam, 2000) pp. 425–461. CrossrefGoogle Scholar
    • B. Fuchs and A. Schulze, A simple 3-approximation of minimum Manhattan networks, Proc. 7th Cologne Twente Workshop on Graphs and Combinatorial Optimization pp. 26–29. Google Scholar
    • J. Gudmundsson, C. Levcopoulos and G. Narasimhan, Approximating a minimum Manhattan network, Nord. J. Computing 8 (2001) 219–232. Preliminary version appeared in Proc. 2nd Int. Workshop on Approximation Algorithms for Combinatorial Optimization, (1999), pp. 28–37 . Google Scholar
    • J. Gudmundssonet al., Small Manhattan networks and algorithms for the Earth Mover's distance, Proc. 23rd European Workshop on Computational Geometry pp. 174–177. Google Scholar
    • Z. Guo, H. Sun and H. Zhu, A fast 2-approximation algorithm for the minimum Manhattan network problem, Proc. 4th Int. Conf. Algorithmic Aspects in Information and Management5034, Lecture Notes in Computer Science (Springer-Verlag, 2008) pp. 212–223. Google Scholar
    • R. Kato, K. Imai and T. Asano, An improved algorithm for the minimum Manhattan network problem, Proc. 13th Int. Symp. Algorithms and Computation2518, Lecture Notes in Computer Science (Springer-Verlag, 2002) pp. 344–356. Google Scholar
    • F. Lam, M. Alexandersson and L. Pachter, J. Comput. Biol. 10, 509 (2003), DOI: 10.1089/10665270360688156. Crossref, ISIGoogle Scholar
    • X. Muñoz, S. Seibert and W. Unger, The minimal Manhattan network problem in three dimensions, Proc. 3rd Int. Workshop on Algorithms and Computation5431, Lecture Notes in Computer Science (Springer-Verlag, 2009) pp. 369–380. Google Scholar
    • K. Nouioua, Enveloppes de Pareto et Réseaux de Manhattan: Caractérisations et algorithmes, Ph.D. thesis, Université de la Méditerranée, 2005 . Google Scholar
    • S. Seibert and W. Unger, A 1.5-approximation of the minimal Manhattan network problem, Proc. 16th Int. Symp. Algorithms and Computation3827, Lecture Notes in Computer Science (Springer-Verlag, 2005) pp. 246–255. Google Scholar
    Remember to check out the Most Cited Articles!

    Check out these titles in image analysis!