文章基本信息

标题：A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread
本地全文：下载
作者：Kyle Fox ; Jiashuai Lu
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：45:1-45:18
DOI：10.4230/LIPIcs.SoCG.2020.45
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Transportation map; earth moverâs distance; shape matching; approximation algorithms