论文标题
确定性的，接近线性$ \ VAREPSILON $ -APPROXIMATION算法几何二分匹配
Deterministic, Near-Linear $\varepsilon$-Approximation Algorithm for Geometric Bipartite Matching
论文作者
论文摘要
给定点集$ a $和$ b $ in $ \ mathbb {r}^d $其中$ a $和$ a $和$ b $具有相等的尺寸$ n $，对于某些常数$ d $和a参数$ \ varepsilon> 0 $，我们提出了第一个确定性算法，该算法计算出，该算法在$ n \ cdot（$ n \ cdot（\ cd）中时间是，在任何$ \ smash {\ ell_p} $ - norm-narm中，在$ a $ a $ a $ a $ a $ a $ a $ a $ b $之间的匹配。尽管Raghvendra和Agarwal提出了具有类似运行时间的蒙特卡洛算法[J. ACM 2020]，这是最著名的确定性$ \ varepsilon $ -Approximation算法占$ω（n^{3/2}）$时间。我们的算法构造了$ \ mathbb {r}^d $的树盖的A（改进），我们开发了几种新工具来采用基于树覆盖的方法来计算$ \ varepsilon $ - 适当的完美匹配。
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 $\varepsilon>0$, we present the first deterministic algorithm that computes, in $n\cdot(\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{\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 $\varepsilon$-approximation algorithm takes $Ω(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 $\varepsilon$-approximate perfect matching.
