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.

The geometric transportation problem takes as input a set of points $P$ in $d$-dimensional Euclidean space and a supply function $μ: P \to \mathbb{R}$. The goal is to find a transportation map, a non-negative assignment $τ: P \times P \to \mathbb{R}_{\geq 0}$ to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., $\sum_{r \in P} τ(q, r) - \sum_{p \in P} τ(p, q) = μ(q)$ for all points $q \in P$. The goal is to minimize the weighted sum of Euclidean distances for the pairs, $\sum_{(p, q) \in P \times P} τ(p, q) \cdot ||q - p||_2$. We describe the first algorithm for this problem that returns, with high probability, a $(1 + \varepsilon)$-approximation to the optimal transportation map in $n\varepsilon^{-O(d)}\log^{O(d)}{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.