Faster algorithms for the geometric transportation problem


Conference Paper

© Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Let R, B C Rd for constant d, be two point sets with |R| + |B| = n, and let λ: R∪B → ℕ such that Σr∈Rλ(r) = Σb∈B λ (b) be demand functions over R and B. Let d(·, ·) be a suitable distance function such as the Lp distance. The transportation problem asks to find a map τ: R × B → ℕ such that Σb∈B τ(r, b) = λ(r), Σr∈Rτ(r, b) = λ(b), and σr∈Rb∈B τ(r, b)d(r, b) is minimized. We present three new results for the transportation problem when d(·, ·) is any Lp metric: • For any constant ϵ > 0, an O(n1+ϵ) expected time randomized algorithm that returns a transportation map with expected cost O(log2(1/ϵ)) times the optimal cost. • For any ϵ > 0, a (1 + ϵ)-approximation in O(n3/2 ϵ-d polylog(U) polylog(n)) time, where U = maxp∈Rcup;B λ (p). •An exact strongly polynomial O(n2 polylogn) time algorithm, for d = 2.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Fox, K; Panigrahi, D; Varadarajan, KR; Xiao, A

Published Date

  • June 1, 2017

Published In

Volume / Issue

  • 77 /

Start / End Page

  • 71 - 716

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959770385

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.SoCG.2017.7

Citation Source

  • Scopus