A deterministic near-linear time approximation scheme for geometric transportation

Kyle Fox and Jiashuai Lu

Submitted on 7 November 2022


Given a set of points P=(P+P)Rd for some constant d and a supply function μ:PR such that μ(p)>0 pP+, μ(p)<0 pP, and pPμ(p)=0, the geometric transportation problem asks one to find a transportation map τ:P+×PR0 such that qPτ(p,q)=μ(p) pP+, pP+τ(p,q)=μ(q) qP, and the weighted sum of Euclidean distances for the pairs (p,q)P+×Pτ(p,q)||qp||2 is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a (1+ε) factor of optimal. More precisely, our algorithm runs in O(nε(d+2)log5nloglogn) time for any constant ε>0. While a randomized nεO(d)logO(d)n time algorithm was discovered in the last few years, all previously known deterministic (1+ε)-approximation algorithms run in Ω(n3/2) time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic nεO(d)logO(d)n time (1+ε)-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known (1+ε)-approximation algorithms, randomized or deterministic, even for geometric bipartite matching, by removing the dependence on the dimension d from the exponent in the running time's polylog.


Comment: 23 pages

Subject: Computer Science - Computational Geometry