Faster Algorithms for the Geometric Transportation Problem
share
Let R and B be two point sets in R^d, with |R|+ |B| = n and where d is a constant. Next, let λ : R ∪ B →N such that ∑_r ∈ R λ(r) = ∑_b ∈ Bλ(b) be demand functions over R and B. Let · be a suitable distance function such as the L_p distance. The transportation problem asks to find a map τ : R × B →N such that ∑_b ∈ Bτ(r,b) = λ(r), ∑_r ∈ Rτ(r,b) = λ(b), and ∑_r ∈ R, b ∈ Bτ(r,b) r-b is minimized. We present three new results for the transportation problem when r-b is any L_p metric: - For any constant ε > 0, an O(n^1+ε) expected time randomized algorithm that returns a transportation map with expected cost O(^2(1/ε)) times the optimal cost. - For any ε > 0, a (1+ε)-approximation in O(n^3/2ε^-dpolylog(U) polylog(n)) time, where U = _p∈ R∪ Bλ(p). - An exact strongly polynomial O(n^2 polylogn) time algorithm, for d = 2.
READ FULL TEXT