针对欧几里德中的完全二分匹配优化的最小成本流 Space
Min Cost Flow Optimized for a Complete Bipartite Matching in Euclidean Space
要点是...我们有两组点 A 和 B。集合A和B的点数相同n。
形式化问题：
在A和B中的点之间构建最小成本完全二分匹配。匹配 (a, b) 的成本是 distance(a, b)。是否存在比 O(n^3) 更快的算法？
备注：
- A中的每个点a和B中的点b 在一个匹配的 (a, b).
中
- A或B中的每个点a正好在一个匹配中
- sum( distance(a, b) 对于每个 (a, b)匹配 ) 最小化。
示例：
- 点a(0,0)
- b点(2,0)
- c点(0,1)
- d点(-2,2)
- 设置 Z {a, d}
- 设置 Y {b, c}
解法：
匹配 1: (a, b) (d, c)
总和(距离(a, b), 距离(d, c) ) = 2 + 开方(5) ~ 4.23
匹配 2: (a, c) (d, b)
总和(距离(a, c), 距离(d, b) ) = 1 + 平方根 (20) ~ 5.47
匹配1(a,b)(d,c)是min cost完全二分匹配！
是的。如果将顶点之间的距离作为它们之间的边的权重，那么这是一个加权二分图。找到 maximum/minimum 权重匹配的任务称为 assignment problem.
使用 Fredman and Tarjan (1987) 中开发的方法可以在 O(|V|(|E|+|V| log |V|) 时间内解决问题。
欧几里得空间还有进一步改进的可能。正如所讨论的 here. Notably, Vaidya (1988) presents a O(n² log n) algorithm for the L1, L2, and L∞ metrics which improves to O(n² (log n)³) for the L1 and L∞ metrics. Agarwal, Efrat, and Sharir (2006, Section 7) 对此进行了改进，给出了一个在 O(n^(2+ε)) 时间内运行的算法。
如果牺牲准确性，您可以做得更好。 Agarwal and Varadarajan (2004) 给出一个概率算法，给定一个值 0<ε<1，在 O(n^(1+ε)) 在最优的乘法 O(log(1/ε)) 内对预期成本进行匹配。
你的点是否恰好位于凸多边形的边缘？然后 Marcotte and Suri (1991) 会很有趣：他们为此提供了一个精确的 O(n log n) 算法。如果多边形是非凸的，但仍然很简单，那么您可以在同一篇论文中使用他们的 O(n² log n) 算法。
要点是...我们有两组点 A 和 B。集合A和B的点数相同n。
形式化问题：
在A和B中的点之间构建最小成本完全二分匹配。匹配 (a, b) 的成本是 distance(a, b)。是否存在比 O(n^3) 更快的算法？
备注：
- A中的每个点a和B中的点b 在一个匹配的 (a, b). 中
- A或B中的每个点a正好在一个匹配中
- sum( distance(a, b) 对于每个 (a, b)匹配 ) 最小化。
示例：
- 点a(0,0)
- b点(2,0)
- c点(0,1)
- d点(-2,2)
- 设置 Z {a, d}
- 设置 Y {b, c}
解法：
匹配 1: (a, b) (d, c)
总和(距离(a, b), 距离(d, c) ) = 2 + 开方(5) ~ 4.23
匹配 2: (a, c) (d, b)
总和(距离(a, c), 距离(d, b) ) = 1 + 平方根 (20) ~ 5.47
匹配1(a,b)(d,c)是min cost完全二分匹配！
是的。如果将顶点之间的距离作为它们之间的边的权重，那么这是一个加权二分图。找到 maximum/minimum 权重匹配的任务称为 assignment problem.
使用 Fredman and Tarjan (1987) 中开发的方法可以在 O(|V|(|E|+|V| log |V|) 时间内解决问题。
欧几里得空间还有进一步改进的可能。正如所讨论的 here. Notably, Vaidya (1988) presents a O(n² log n) algorithm for the L1, L2, and L∞ metrics which improves to O(n² (log n)³) for the L1 and L∞ metrics. Agarwal, Efrat, and Sharir (2006, Section 7) 对此进行了改进，给出了一个在 O(n^(2+ε)) 时间内运行的算法。
如果牺牲准确性，您可以做得更好。 Agarwal and Varadarajan (2004) 给出一个概率算法，给定一个值 0<ε<1，在 O(n^(1+ε)) 在最优的乘法 O(log(1/ε)) 内对预期成本进行匹配。
你的点是否恰好位于凸多边形的边缘？然后 Marcotte and Suri (1991) 会很有趣：他们为此提供了一个精确的 O(n log n) 算法。如果多边形是非凸的，但仍然很简单，那么您可以在同一篇论文中使用他们的 O(n² log n) 算法。