Deterministic, near-linear ? -approximation algorithm for geometric bipartite matching
Deterministic, near-linear ? -approximation algorithm for geometric bipartite matching
复制标题
确定性、近线性 ?
DOI：
10.1145/3519935.3519977
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Xiao, Allen
中科院分区：
文献类型：
--
作者：
Agarwal, Pankaj K.;Chang, Hsien-Chih;Raghvendra, Sharath;Xiao, Allen
给定两个点集A和Bin的大小均为d，对于某个常数维数n ≥ 1，参数ε>0，我们给出了一个确定性算法，该算法在n·（ε− 1 logn）O（d）时间内计算出A和B之间的完美匹配，其代价在任何范数下都在最优匹配的（1+ε）因子之内.尽管Raghvendra和Agarwal [J. ACM 2020]提出了具有类似运行时间的蒙特-卡罗算法，但最著名的确定性ε-近似算法需要Ω（n3/2）时间。我们的算法构造了一个（细化）的树覆盖，我们开发了几个新的工具来应用基于树覆盖的方法来计算一个ε-近似完美匹配。
Given two point setsAandBin ℝdof sizeneach, for some constant dimensiond≥ 1, and a parameter ε>0, we present a deterministic algorithm that computes, inn·(ε−1logn)O(d)time, a perfect matching betweenAandBwhose cost is within a (1+ε) factor of the optimal matching under any ℓ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 ε-approximation algorithm takes Ω(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 ε-approximate perfect matching.