# Deterministic, Near-Linear varepsilon-Approximation Algorithm for Geometric Bipartite Matching

arXiv: https://arxiv.org/abs/2204.03875 · HTML: https://mlsanity.com/paper/2204.03875/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2022.

## Built on by (most cited first, 1 of 1)

- [Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair](https://mlsanity.com/paper/2508.06774/) (2025)

## Abstract (arXiv)

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