Document Open Access Logo

An Improved ε-Approximation Algorithm for Geometric Bipartite Matching

Authors Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, Rachita Sowle

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.6.pdf
  • Filesize: 0.95 MB
  • 20 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
  • Duke University, Durham, NC, USA
Sharath Raghvendra
  • Virginia Tech, Blacksburg, VA, USA
Pouyan Shirzadian
  • Virginia Tech, Blacksburg, VA, USA
Rachita Sowle
  • Virginia Tech, Blacksburg, VA, USA

Funding

Work on this paper was supported by NSF under grant CCF 1909171.

Cite As Get BibTex

Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle. An Improved ε-Approximation Algorithm for Geometric Bipartite Matching. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SWAT.2022.6

Abstract

For two point sets A, B ⊂ ℝ^d, with |A| = |B| = n and d > 1 a constant, and for a parameter ε > 0, we present a randomized algorithm that, with probability at least 1/2, computes in O(n(ε^{-O(d³)}log log n + ε^{-O(d)}log⁴ nlog⁵log n)) time, an ε-approximate minimum-cost perfect matching under any L_p-metric. All previous algorithms take n(ε^{-1}log n)^{Ω(d)} time. We use a randomly-shifted tree, with a polynomial branching factor and O(log log n) height, to define a tree-based distance function that ε-approximates the L_p metric as well as to compute the matching hierarchically. Then, we apply the primal-dual framework on a compressed representation of the residual graph to obtain an efficient implementation of the Hungarian-search and augment operations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Euclidean bipartite matching
  • approximation algorithms
  • primal dual method

Metrics

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

References

  1. Pankaj Agarwal and Kasturi Varadarajan. A near-linear constant-factor approximation for Euclidean bipartite matching? In Proceedings of the twentieth annual symposium on Computational geometry, page 247, 2004. Google Scholar
  2. Pankaj K Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao. Deterministic, near-linear ε-approximation algorithm for geometric bipartite matching. arXiv preprint arXiv:2204.03875, 2022. Google Scholar
  3. A. Andoni, K. D. Ba, P. Indyk, and D. P. Woodruff. Efficient sketches for earth-mover distance, with applications. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 324-330, 2009. Google Scholar
  4. Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proc. 34th International Conference on Machine Learning, pages 214-223, 2017. Google Scholar
  5. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67-90, January 1995. Google Scholar
  6. Moses Charikar. Similarity estimation techniques from rounding algorithms. In Proc. 34th Annu. ACM Sympos. Theory Comput., pages 380-388, 2002. Google Scholar
  7. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 448-455, 2003. Google Scholar
  8. Kyle Fox and Jiashuai Lu. A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread. In Proc. 36th Annual Symposium on Computational Geometry, pages 45:1-45:18, 2020. Google Scholar
  9. H. N. Gabow and R.E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18:1013-1036, 1989. Google Scholar
  10. Sariel Har-Peled. Geometric approximation algorithms, 2011. Google Scholar
  11. Piotr Indyk. A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In SODA 2007, page 4, 2007. Google Scholar
  12. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2495-2504, 2017. Google Scholar
  13. Harold Kuhn. Variants of the hungarian method for assignment problems. Naval Research Logistics, 3(4):253-258, 1956. Google Scholar
  14. Nathaniel Lahn and Sharath Raghvendra. An O(n^5/4) time ε-approximation algorithm for RMS matching in a plane. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pages 869-888, 2021. Google Scholar
  15. Marcin Mucha and Piotr Sankowski. Maximum matchings via gaussian elimination. 45th Annual IEEE Symposium on Foundations of Computer Science, pages 248-255, 2004. Google Scholar
  16. Sharath Raghvendra and Pankaj K. Agarwal. A near-linear time ε-approximation algorithm for geometric bipartite matching. Journal of the ACM, 67(3):1-19, June 2020. Google Scholar
  17. Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. The earth mover’s distance as a metric for image retrieval. International Journal of Computer Vision, 40(2):99-121, 2000. Google Scholar
  18. R. Sharathkumar. A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates. In 29th International Symposium on Computational Geometry, pages 9-16, 2013. URL: https://doi.org/10.1145/2462356.2480283.
  19. R. Sharathkumar and P. K. Agarwal. Algorithms for transportation problem in geometric settings. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 306-317, 2012. Google Scholar
  20. Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics, 34(4):66, 2015. Google Scholar
  21. Jan van den Brand, Danupon Nanongkai Yin-Tat Lee, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. IEEE 61st Annual Symposium on Foundations of Computer Science, pages 919-930, 2020. 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