Given two point sets $A$ and $B$ in $\mathbb{R}^d$ of size $n$ each, for some constant $d$, and a constant $\varepsilon>0$, we present the first deterministic algorithm that computes, in $O(n \mathop{\mathrm{polylog}}(n))$ time, a perfect matching between $A$ and $B$ whose cost is within a $1+\varepsilon$ factor of the optimal matching under $L_p$ norm. Although a Monte-Carlo algorithm with a similar running time was proposed by Raghvendra and Agarwal nearly a decade ago, the best-known deterministic eps-approximation algorithm takes at least $n^{3/2}$ time in the worst case. 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 eps-approximate perfect matching.
This is a joint work with Hsien-Chih Chang, Sharathkumar Raghvendra, and Allen Xiao.