When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.6
URN: urn:nbn:de:0030-drops-161660
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16166/
 Go to the corresponding LIPIcs Volume Portal

### An Improved ε-Approximation Algorithm for Geometric Bipartite Matching

 pdf-format:

### 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.

### BibTeX - Entry

@InProceedings{agarwal_et_al:LIPIcs.SWAT.2022.6,
author =	{Agarwal, Pankaj K. and Raghvendra, Sharath and Shirzadian, Pouyan and Sowle, Rachita},
title =	{{An Improved \epsilon-Approximation Algorithm for Geometric Bipartite Matching}},
booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages =	{6:1--6:20},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-236-5},
ISSN =	{1868-8969},
year =	{2022},
volume =	{227},
editor =	{Czumaj, Artur and Xin, Qin},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
}