Given a set of points $P=({P}^{+}\bigsqcup {P}^{-})\subset {\mathbb{R}}^{d}$ for some
constant $d$ and a supply function $\mu :P\to \mathbb{R}$ such that $\mu (p)>0\text{}\mathrm{\forall}p\in {P}^{+}$ , $\mu (p)<0\text{}\mathrm{\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)\text{}\mathrm{\forall}p\in {P}^{+}$ , $\sum _{p\in {P}^{+}}\tau (p,q)=-\mu (q)\text{}\mathrm{\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+\epsilon )$ factor of optimal. More precisely, our algorithm runs in
$O(n{\epsilon}^{-(d+2)}{\mathrm{log}}^{5}n\mathrm{log}\mathrm{log}n)$ time for any constant
$\epsilon >0$ . While a randomized $n{\epsilon}^{-O(d)}{\mathrm{log}}^{O(d)}n$ time
algorithm was discovered in the last few years, all previously known
deterministic $(1+\epsilon )$ -approximation algorithms run in
$\mathrm{\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{\epsilon}^{-O(d)}{\mathrm{log}}^{O(d)}n$ time $(1+\epsilon )$ -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+\epsilon )$ -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

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

Kyle Fox and Jiashuai Lu

Submitted on 7 November 2022

## Abstract

## Preprint

Comment: 23 pages

Subject: Computer Science - Computational Geometry