摘要：The geometric transportation problem takes as input a set of points P in d-dimensional Euclidean space and a supply function μ : P â' â". The goal is to find a transportation map, a non-negative assignment Ï" : P Ã- P â' â"_{⥠0} to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., â^'_{r â^^ P} Ï"(q, r) - â^'_{p â^^ P} Ï"(p, q) = μ(q) for all points q â^^ P. The goal is to minimize the weighted sum of Euclidean distances for the pairs, â^'_{(p, q) â^^ P Ã- P} Ï"(p, q) â<. q - p â,,. We describe the first algorithm for this problem that returns, with high probability, a (1 + ε)-approximation to the optimal transportation map in O(n poly(1 / ε) polylog n) time. In contrast to the previous best algorithms for this problem, our near-linear running time bound is independent of the spread of P and the magnitude of its real-valued supplies.
