Deterministic, near-linear-approximation algorithm for geometric bipartite matching

Conference Paper

Given two point sets A and B in g.,d of size n each, for some constant dimension d≥ 1, and a parameter ϵ>0, we present a deterministic algorithm that computes, in n·(ϵ-1 logn)O(d) time, a perfect matching between A and B whose cost is within a (1+ϵ) factor of the optimal matching under any g.,"p-norm. Although a Monte-Carlo algorithm with a similar running time is proposed by Raghvendra and Agarwal [J. ACM 2020], the best-known deterministic ϵ-approximation algorithm takes ω(n3/2) time. Our algorithm constructs a (refinement of a) tree cover of g.,d, and we develop several new tools to apply a tree-cover based approach to compute an ϵ-approximate perfect matching.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Chang, HC; Raghvendra, S; Xiao, A

Published Date

  • September 6, 2022

Published In

Start / End Page

  • 1052 - 1065

International Standard Serial Number (ISSN)

  • 0737-8017

International Standard Book Number 13 (ISBN-13)

  • 9781450392648

Digital Object Identifier (DOI)

  • 10.1145/3519935.3519977

Citation Source

  • Scopus