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