A deterministic near-linear time approximation scheme for geometric transportation

Given a set of points $P=\left(P^{+} \sqcup P^{-}\right) \subset \mathbb{R}^{d}$ for some constant d and a supply function $\mu: P \rightarrow \mathbb{R}$ such that $\mu(p)\gt$ $0 \forall p \in P^{+}, \mu(p)\lt 0 \forall p \in P^{-}$, and $\sum_{p \in P} \mu(p)=0$, the geometric transportation problem asks one to find a transportation map $\tau: P^{+} \times P^{-} \rightarrow \mathbb{R}_{\geq 0}$ such that $\sum_{q \in P^{-}} \tau(p, q)=\mu(p) \forall p \in P^{+}$, $\sum_{p \in P^{+}} \tau(p, q)=-\mu(q) \forall q \in P^{-}$, and the weighted sum of Euclidean distances for the pairs $\sum_{(p, q) \in P^{+} \times P^{-}} \tau(p, q) \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 $(1+\varepsilon)$ factor of optimal. More precisely, our algorithm runs in $O\left(n \varepsilon^{-(d+2)} \log ^{5} n \log \log n\right)$ time for any constant $\varepsilon>0$. While a randomized $n \varepsilon^{-O(d)} \log ^{O(d)} n$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $(1+\varepsilon)$-approximation algorithms run in $\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 \varepsilon^{-O(d)} \log ^{O(d)} n$ time $(1+\varepsilon)$-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+\varepsilon)$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $(1+\varepsilon)$-approximate deterministic algorithm for geometric bipartite matching and the first $(1+\varepsilon)$ approximate deterministic or randomized algorithm for geometric transportation with no dependence on d in the exponent of the running time’s polylog. As an additional application of our main ideas, we also give the first randomized near-linear $O\left(\varepsilon^{-2} m \log ^{O(1)} n\right)$ time $(1+\varepsilon)$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary real edge costs.