License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.6
URN: urn:nbn:de:0030-drops-161660
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16166/
Agarwal, Pankaj K. ;
Raghvendra, Sharath ;
Shirzadian, Pouyan ;
Sowle, Rachita
An Improved ε-Approximation Algorithm for Geometric Bipartite Matching
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},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16166},
URN = {urn:nbn:de:0030-drops-161660},
doi = {10.4230/LIPIcs.SWAT.2022.6},
annote = {Keywords: Euclidean bipartite matching, approximation algorithms, primal dual method}
}
Keywords: |
|
Euclidean bipartite matching, approximation algorithms, primal dual method |
Collection: |
|
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
22.06.2022 |