Document Open Access Logo

Approximating Longest Spanning Tree with Neighborhoods

Author Ahmad Biniaz

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.7.pdf
  • Filesize: 0.78 MB
  • 11 pages

Document Identifiers

Author Details

Ahmad Biniaz
  • School of Computer Science, University of Windsor, Canada

Funding

Supported by NSERC.

Cite As Get BibTex

Ahmad Biniaz. Approximating Longest Spanning Tree with Neighborhoods. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.7

Abstract

We study the following maximization problem in the Euclidean plane: Given a collection of neighborhoods (polygonal regions) in the plane, the goal is to select a point in each neighborhood so that the longest spanning tree on selected points has maximum length. It is not known whether or not this problem is NP-hard. We present an approximation algorithm with ratio 0.548 for this problem. This improves the previous best known ratio of 0.511. 
The presented algorithm takes linear time after computing a diameter. Even though our algorithm itself is fairly simple, its analysis is rather involved. In some part we deal with a minimization problem with multiple variables. We use a sequence of geometric transformations to reduce the number of variables and simplify the analysis.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Euclidean maximum spanning tree
  • spanning tree with neighborhoods
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K. Agarwal, Jirí Matousek, and Subhash Suri. Farthest neighbors, maximum spanning trees and related problems in higher dimensions. Comput. Geom., 1:189-201, 1991. Google Scholar
  2. Noga Alon, Sridhar Rajagopalan, and Subhash Suri. Long non-crossing configurations in the plane. Fundam. Inform., 22(4):385-394, 1995. Also in SoCG 1993. Google Scholar
  3. Esther M. Arkin and Refael Hassin. Approximation algorithms for the geometric covering salesman problem. Discret. Appl. Math., 55(3):197-218, 1994. Google Scholar
  4. Tetsuo Asano, Binay K. Bhattacharya, J. Mark Keil, and F. Frances Yao. Clustering algorithms based on minimum and maximum spanning trees. In Proceedings of the 4th Annual Symposium on Computational Geometry (SoCG), pages 252-257, 1988. Google Scholar
  5. Marshall Bern and David Eppstein. Approximation algorithms for geometric problems. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 296-345. PWS Publishing, 1996. Google Scholar
  6. Binay K. Bhattacharya and Godfried T. Toussaint. Efficient algorithms for computing the maximum distance between two finite planar sets. J. Algorithms, 4(2):121-136, 1983. Google Scholar
  7. Ahmad Biniaz, Prosenjit Bose, David Eppstein, Anil Maheshwari, Pat Morin, and Michiel Smid. Spanning trees in multipartite geometric graphs. Algorithmica, 80(11):3177-3191, 2018. Google Scholar
  8. Víctor Blanco, Elena Fernández, and Justo Puerto. Minimum spanning trees with neighborhoods: Mathematical programming formulations and solution methods. Eur. J. Oper. Res., 262(3):863-878, 2017. Google Scholar
  9. Bernard Chazelle and Jirí Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms, 21(3):579-597, 1996. Google Scholar
  10. Ke Chen and Adrian Dumitrescu. On the longest spanning tree with neighborhoods. Discrete Mathematics, Algorithms and Applications, 12(5), 2020. Also in FAW'18. Google Scholar
  11. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. Google Scholar
  12. Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars, and A. Frank van der Stappen. TSP with neighborhoods of varying size. J. Algorithms, 57(1):22-36, 2005. Also in ESA 2002. Google Scholar
  13. Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro López-Ortiz, and Diego Seco. On minimum- and maximum-weight minimum spanning trees with neighborhoods. Theory Comput. Syst., 56(1):220-250, 2015. Google Scholar
  14. Adrian Dumitrescu and Csaba D. Tóth. Long non-crossing configurations in the plane. Discret. Comput. Geom., 44(4):727-752, 2010. Also in STACS 2010. Google Scholar
  15. G. A. Galperin. A concept of the mass center of a system of material points in the constant curvature spaces. Communications in Mathematical Physics, 154(1):63-84, 1993. Google Scholar
  16. Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 585-594, 2003. Google Scholar
  17. Maarten Löffler. Data Imprecision in Computational Geometry. Phd thesis, Utrecht University, 2009. Google Scholar
  18. Maarten Löffler and Marc J. van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 56(2):235-269, 2010. Google Scholar
  19. Nimrod Megiddo. Linear-time algorithms for linear programming in ℝ³ and related problems. SIAM J. Comput., 12(4):759-776, 1983. Also in FOCS 1982. Google Scholar
  20. Joseph S. B. Mitchell. A PTAS for TSP with neighborhoods among fat regions in the plane. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 11-18, 2007. Google Scholar
  21. Joseph S. B. Mitchell. A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane. In Proceedings of the 26th ACM Symposium on Computational Geometry (SoCG), pages 183-191, 2010. Google Scholar
  22. Clyde L. Monma, Mike Paterson, Subhash Suri, and F. Frances Yao. Computing Euclidean maximum spanning trees. Algorithmica, 5(3):407-419, 1990. Google Scholar
  23. Marc J. van Kreveld and Maarten Löffler. Approximating largest convex hulls for imprecise points. J. Discrete Algorithms, 6(4):583-594, 2008. Google Scholar
  24. Emo Welzl. Smallest enclosing disks (balls and ellipsoids). In Maurer H. (eds) New Results and New Trends in Computer Science, pages 359-370. LNCS 555, 1991. Google Scholar
  25. Yang Yang, Mingen Lin, Jinhui Xu, and Yulai Xie. Minimum spanning tree with neighborhoods. In Proceedings of the 3rd International ConferenceAlgorithmic Aspects in Information and Management (AAIM), pages 306-316, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact