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

Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra +1

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 determini…