PREPRINT

# A deterministic near-linear time approximation scheme for geometric transportation

Kyle Fox and Jiashuai Lu

Submitted on 7 November 2022

## Abstract

Given a set of points $P=\left({P}^{+}\bigsqcup {P}^{-}\right)\subset {\mathbb{R}}^{d}$ for some constant $d$ and a supply function $\mu :P\to \mathbb{R}$ such that , , and $\sum _{p\in P}\mu \left(p\right)=0$, the geometric transportation problem asks one to find a transportation map $\tau :{P}^{+}×{P}^{-}\to {\mathbb{R}}_{\ge 0}$ such that , , and the weighted sum of Euclidean distances for the pairs $\sum _{\left(p,q\right)\in {P}^{+}×{P}^{-}}\tau \left(p,q\right)\cdot ||q-p|{|}_{2}$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $\left(1+\epsilon \right)$ factor of optimal. More precisely, our algorithm runs in $O\left(n{\epsilon }^{-\left(d+2\right)}{\mathrm{log}}^{5}n\mathrm{log}\mathrm{log}n\right)$ time for any constant $\epsilon >0$. While a randomized $n{\epsilon }^{-O\left(d\right)}{\mathrm{log}}^{O\left(d\right)}n$ time algorithm was discovered in the last few years, all previously known deterministic $\left(1+\epsilon \right)$-approximation algorithms run in $\mathrm{\Omega }\left({n}^{3/2}\right)$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $n{\epsilon }^{-O\left(d\right)}{\mathrm{log}}^{O\left(d\right)}n$ time $\left(1+\epsilon \right)$-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 $\left(1+\epsilon \right)$-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.

## Preprint

Comment: 23 pages

Subject: Computer Science - Computational Geometry