An Improved ϵ-Approximation Algorithm for Geometric Bipartite Matching

Conference Paper

For two point sets A,B ⊂ Rd, 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(d3) log log n + ϵ-O(d) log4 n log5 log n)) time, an ϵ-approximate minimum-cost perfect matching under any Lp-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 Lp 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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Raghvendra, S; Shirzadian, P; Sowle, R

Published Date

  • June 1, 2022

Published In

Volume / Issue

  • 227 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959772365

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.SWAT.2022.6

Citation Source

  • Scopus