Faster Algorithms for the Geometric Transportation Problem

Let R and B be two point sets in ℝd, with |R|+ |B| = n and where d is a constant. Next, let λ : R cup B → mathbbN such that sumr ∈ R λ(r) = sumb ∈ B λ(b) be demand functions over R and B. Let |·| be a suitable distance function such as the Lp distance. The transportation problem asks to find a map τ : R × B → mathbbN such that sumb ∈ Bτ(r,b) = λ(r), sumr ∈ Rτ(r,b) = λ(b), and sumr ∈ R, b ∈ B τ(r,b) |r-b| is minimized. We present three new results for the transportation problem when |r-b| is any Lp metric: - For any constant varepsilon > 0, an O(n1+varepsilon) expected time randomized algorithm that returns a transportation map with expected cost O(log2(1/varepsilon)) times the optimal cost. - For any varepsilon > 0, a (1+varepsilon)-approximation in O(n3/2varepsilon-d operatornamepolylog(U) operatornamepolylog(n)) time, where U = maxp∈ Rcup B λ(p). - An exact strongly polynomial O(n2 operatornamepolylogn) time algorithm, for d = 2.