LIPIcs.SoCG.2022.47.pdf
- Filesize: 0.78 MB
- 13 pages
Document
Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs
Authors
Sariel Har-Peled 
,
-
Part of:
Volume:
38th International Symposium on Computational Geometry (SoCG 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-01
File
Document Identifiers
Author Details
Acknowledgements
The authors thank the anonymous referees for their detailed comments.
Cite As Get BibTex
Sariel Har-Peled and Everett Yang. Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.47
Abstract
We present a (1-ε)-approximation algorithms for maximum cardinality matchings in disk intersection graphs - all with near linear running time. We also present an estimation algorithm that returns (1±ε)-approximation to the size of such matchings - this algorithm runs in linear time for unit disks, and O(n log n) for general disks (as long as the density is relatively small).
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Matchings
- disk intersection graphs
- approximation algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Boris Aronov and Sariel Har-Peled. On approximating the depth and related problems. SIAM J. Comput., 38(3):899-921, 2008. URL: https://doi.org/10.1137/060669474.
- Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge estimation with independent set oracles. ACM Trans. Algo., 16(4), September 2020. URL: https://doi.org/10.1145/3404867.
- Édouard Bonnet, Sergio Cabello, and Wolfgang Mulzer. Maximum matchings in geometric intersection graphs. In Christophe Paul and Markus Bläser, editors, Proc. 37th Internat. Sympos. Theoret. Asp. Comp. Sci. (STACS), volume 154 of LIPIcs, pages 31:1-31:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.31.
- Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications. Springer, Santa Clara, CA, USA, 3rd edition, 2008. URL: https://doi.org/10.1007/978-3-540-77974-2.
- Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. J. ACM, 61(1), January 2014. URL: https://doi.org/10.1145/2529989.
- Alon Efrat, Alon Itai, and Matthew J. Katz. Geometry helps in bottleneck matching and related problems. Algorithmica, 31(1):1-28, 2001. URL: https://doi.org/10.1007/s00453-001-0016-8.
- Harold N. Gabow and Robert Endre Tarjan. Faster scaling algorithms for general graph-matching problems. J. Assoc. Comput. Mach., 38(4):815-853, 1991. URL: https://doi.org/10.1145/115234.115366.
- Sariel Har-Peled. A simple proof of the existence of a planar separator. ArXiv e-prints, April 2013. URL: http://arxiv.org/abs/1105.0103.
- Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput., 46(6):1712-1744, 2017. URL: https://doi.org/10.1137/16M1079336.
- Sariel Har-Peled and Everett Yang. Approximation algorithms for maximum matchings in geometric intersection graphs. CoRR, abs/2201.01849, 2022. URL: http://arxiv.org/abs/2201.01849.
- Nicholas J. A. Harvey. Algebraic algorithms for matching and matroid problems. SIAM J. Comput., 39(2):679-702, 2009. URL: https://doi.org/10.1137/070684008.
- John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: https://doi.org/10.1137/0202019.
- Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. Discrete Comput. Geom., 64(3):838-904, September 2020. URL: https://doi.org/10.1007/s00454-020-00243-7.
- Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved distributed approximate matching. J. Assoc. Comput. Mach., 62(5):38:1-38:17, 2015. URL: https://doi.org/10.1145/2786753.
- Marcin Mucha and Piotr Sankowski. Maximum matchings via gaussian elimination. In Proc. 45th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 248-255. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.40.
- Marcin Mucha and Piotr Sankowski. Maximum matchings in planar graphs via Gaussian elimination. Algorithmica, 45(1):3-20, 2006. URL: https://doi.org/10.1007/s00453-005-1187-5.
- Raphael Yuster and Uri Zwick. Maximum matching in graphs with an excluded minor. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proc. 18th ACM-SIAM Sympos. Discrete Algs. (SODA), pages 108-117. SIAM, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283396.