2026-07-26T04:14:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16166 2024-03-06T10:57:03Z ddc:004 open_access

An Improved ε-Approximation Algorithm for Geometric Bipartite Matching Agarwal, Pankaj K. Raghvendra, Sharath Shirzadian, Pouyan Sowle, Rachita Euclidean bipartite matching approximation algorithms primal dual method 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Sharath Raghvendra and Pouyan Shirzadian and Rachita Sowle 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.6 urn:nbn:de:0030-drops-161660 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode