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

Given point sets 𝐴 and 𝐵 in R 𝑑 where 𝐴 and 𝐵 have equal size 𝑛 for some constant dimension 𝑑 and a parameter 𝜀 > 0, we present the first deterministic algorithm that computes, in 𝑛 • (𝜀 -1 log 𝑛) 𝑂 (𝑑) time, a perfect matching between 𝐴 and 𝐵 whose cost is within a (1 + 𝜀) factor of the optimal under any ℓ 𝑝 -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 Ω(𝑛 3/2 ) time. Our algorithm constructs a (refinement of a) tree cover of R 𝑑 , and we develop several new tools to apply a tree-cover based approach to compute an 𝜀-approximate perfect matching.