A near-linear constant-factor approximation for euclidean bipartite matching?
A near-linear constant-factor approximation for euclidean bipartite matching?
复制标题
欧氏二分匹配的近线性常数因子近似？
DOI：
10.1145/997817.997856
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Kasturi R. Varadarajan
中科院分区：
文献类型：
--
作者：
P. Agarwal;Kasturi R. Varadarajan
在欧几里德二分匹配问题中，我们给出了一个<i></i>“红”点集R和一<i></i>个“蓝”点<sup>集B，</sup>其中|<i>R</i>| = |<i>B</i>| = <i>n</i>，我们希望将每个红点与一个不同的蓝点配对，以便使配对点之间的距离之和最小化。我们提出了一个近似算法，给定任何参数0 <<i>ε</i>< 1运行在<i>O</i>（<i>n1</i><sup>+ε</sup>）的期望时间，并返回一个匹配的期望成本是在一个乘法因子<i>O</i>（log（1/<i>ε</i>））的最佳。尺寸<i>d</i>被认为是固定常数。
In the Euclidean bipartite matching problem, we are given a set <i>R</i> of "red" points and a set <i>B</i> of "blue" points in ℝ<sup>3</sup> where |<i>R</i>| = |<i>B</i>| = <i>n</i>, and we want to pair up each red point with a distinct blue point so that the sum of distances between the paired points is minimized. We present an approximation algorithm that given any parameter 0 < <i>ε</i> < 1 runs in <i>O</i>(<i>n</i><sup>1+ε</sup>) expected time and returns a matching whose expected cost is within a multiplicative factor <i>O</i>(log (1/<i>ε</i>)) of the optimal. The dimension <i>d</i> is considered to be a fixed constant.