A deterministic near-linear time approximation scheme for geometric transportation

Joint work with Jiashaui Lu

Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS), 1301–1315, 2023

pdf

Abstract

Given a set of points \(P = (P^+ \sqcup P^-) \subset \mathbb{R}^d\) for some constant \(d\) and a supply function \(\mu:P\to \mathbb{R}\) such that \(\mu(p) > 0~\forall p \in P^+\), \(\mu(p) < 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^-\to \mathbb{R}_{\ge 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(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})\) 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(n^{3/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\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(\varepsilon^{-2} m \log^{O(1)} n)\) time \((1 + \varepsilon)\)-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary real edge costs.