Deterministic, Near-Linear $\epsilon$-Approximation Algorithm for Geometric Bipartite Matching

Abstract

Given point sets $A$ and $B$ in ${\mathbb{R}}^d$ where $A$ and $B$ have equal size $n$ for some constant dimension $d$ and a parameter $\epsilon >0$, we present the first deterministic algorithm that computes, in $n\cdot ({\epsilon }^{-1}\log n{)}^{O(d)}$ time, a perfect matching between $A$ and $B$ whose cost is within a $(1+\epsilon )$ factor of the optimal under any ${\ell }_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 $\epsilon$-approximation algorithm takes $\Omega (n^{3/2})$ time. Our algorithm constructs a (refinement of a) tree cover of ${\mathbb{R}}^d$, and we develop several new tools to apply a tree-cover based approach to compute an $\epsilon$-approximate perfect matching.

The conference version of the paper is accepted to STOC 2022