Translated title: (A deterministic near-linear time approximation scheme for geometric transportation)

from arxiv, Update 1: Adds a new randomized near-linear time approximation scheme for uncapacitated minimum cost flow in undirected graphs (transshipment) with arbitrary edge costs. References more recent work in geometric bipartite matching. 26 pages

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$. Surprisingly, our result is not only a generalization of a 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(poly(1 / \varepsilon) 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.

翻译：- 基于几何传输的确定性近线性时间逼近方案 Translated abstract：给定一个点集 $P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$（其中 $d$ 是一个常量）和一个供应函数 $\mu:P\to \mathbb{R}$，使得 $\mu(p) > 0~\forall p \in P^+$，$\mu(p) < 0~\forall p \in P^-$，且 $\sum_{p\in P}{\mu(p)} = 0$。几何传输问题要求找到一张传输图 $\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$，满足 $\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^-$，并且对于成对点 $(p,q)\in P^+\times P^-$ 来讲的加权欧几里得距离 $\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$ 最小。我们提出了第一个确定性算法，可以在近线性时间内计算出成本在最优解的 $(1 + \varepsilon)$ 倍以内的传输图。具体地，我们的算法对于任意常数 $\varepsilon > 0$，运行时间为 $O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$。令人惊讶的是，我们的结果不仅是 bipartite matching 问题的一个推广，也减少了所有已知的 $(1 + \varepsilon)$-近似算法的运行时间，无论是随机还是确定性的算法，即使是对于几何 bipartite matching 问题也是如此。特别地，我们提供了第一个几何 bipartite matching 的 $(1 + \varepsilon)$-近似确定性算法，以及第一个对任意实边成本的无容量最小成本流 (transshipment) 问题的 $(1 + \varepsilon)$-近似随机或确定性算法，其运行时间的 polylog 求职不依赖于 $d$。作为我们主要思想的另一个应用，我们还提供了第一个随机近线性的 $O(poly(1 / \varepsilon) m \log^{O(1)} n)$ 时间 $(1 + \varepsilon)$-近似算法，该算法用于求解具有任意实边成本的无向图中的无容量最小成本流(transshipment) 问题。