Faster Algorithms for the Geometric Transportation Problem
Faster Algorithms for the Geometric Transportation Problem
复制标题
几何运输问题的更快算法
DOI：
10.4230/lipics.socg.2017.7
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Allen Xiao
中科院分区：
文献类型：
--
作者：
P. Agarwal;K. Fox;Debmalya Panigrahi;Kasturi R. Varadarajan;Allen Xiao
令R，B为r^d中的一组n个点，对于d，r的点具有整数供应，b的点具有整数需求，并且供应之和等于需求之和。令D（。，。）为合适的距离函数，例如L_P距离。运输问题要求找到一个地图tau：r x b-> n，以便sum_ {b} b} tau（r，b）= sump sum_ {r} r} tau（r，b）=需求（b）和sum_ {r in r，b in b} tau（r，b）d（r，b）被最小化。当d（。，。）是任何L_P度量时，我们为运输问题提供了三个新结果：
*对于任何常数epsilon> 0，o（n^{1+epsilon}）预期时间随机算法，该算法返回带有预期成本o（log^2（1/epsilon））乘以最佳成本的运输图。
*对于任何epsilon> 0，a（1+epsilon） - o（n^{3/2} epsilon^{ - d} polylog（u）polyg（n））时间的approximation，其中u是最大供应或需求任何点。
*精确的强烈多项式O（n^2 polylog n）时间算法，对于d = 2。
Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric:
* For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost.
* For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point.
* An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.