Algorithms for the transportation problem in geometric settings
Algorithms for the transportation problem in geometric settings
复制标题
几何设置中的运输问题的算法
DOI：
10.1137/1.9781611973099.29
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
P. Agarwal
中科院分区：
文献类型：
--
作者：
R. Sharathkumar;P. Agarwal
对于A， B∧Rd, |A| + |B| = n，设A e A有需求da e Z+， B e B有供给sb e Z+， [EQUATION] = U，设d（.,.）为距离函数。假设A∪B的直径在d（.,.）下为Δ，而e∪B是一个参数。我们提出了一种算法，该算法在O(（n√Ulog2 n + Ulog U）Φ（n) log（ΔU/e））时间内计算出a， B上运输问题的解，该解与最优解的相加误差为e。其中Φ(n)为距离函数d（.,.）下动态加权最近邻数据结构的查询和更新时间。注意（1/e）只出现在对数项中。在我们得到的各种结果中，
For A, B ⊂ Rd, |A| + |B| = n, let a e A have a demand da e Z+ and b e B have a supply sb e Z+, [EQUATION] = U and let d(.,.) be a distance function. Suppose the diameter of A ∪ B is Δ under d(.,.), and e > 0 is a parameter. We present an algorithm that in O((n√Ulog2 n + U log U)Φ(n) log(ΔU/e)) time computes a solution to the transportation problem on A, B which is within an additive error e from the optimal solution. Here Φ(n) is the query and update time of a dynamic weighted nearest neighbor data structure under distance function d(.,.). Note that the (1/e) appears only in the log term. As among various consequences we obtain,
• For A, B ⊂ Rd and for the case where d(.,.) is a metric, an e-approximation algorithm for the transportation problem in O((n√U log2 n + U log U)Φ(n) log (U/e)) time.
• For A, B ⊂ [Δ]d and the L1 and L∞ distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O(n3/2 log d+O(1) n log Δ) time.
• For A, B ⊂ [Δ]2 and RMS distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O(n3/2+δ log Δ) time, for an arbitrarily small constant δ > 0.
For point sets, A, B ⊂ [Δ]d, for the Lp norm and for 0 < α, β < 1, we present a randomized dynamic data structure that maintains a partial solution to the transportation problem under insertions and deletions of points in which at least (1 − α)U of the demands are satisfied and whose cost is within (1 + β) of that of the optimal (complete) solution to the transportation problem with high probability. The insertion, deletion and update times are O(poly(log(nΔ)/αβ)), provided U = nO(1).