Skip to main content

Faster algorithms for the geometric transportation problem

Publication ,  Conference
Agarwal, PK; Fox, K; Panigrahi, D; Varadarajan, KR; Xiao, A
Published in: Leibniz International Proceedings in Informatics, LIPIcs
June 1, 2017

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.

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959770385

Publication Date

June 1, 2017

Volume

77

Start / End Page

71 / 716

Related Subject Headings

  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Agarwal, P. K., Fox, K., Panigrahi, D., Varadarajan, K. R., & Xiao, A. (2017). Faster algorithms for the geometric transportation problem. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 77, pp. 71–716). https://doi.org/10.4230/LIPIcs.SoCG.2017.7
Agarwal, P. K., K. Fox, D. Panigrahi, K. R. Varadarajan, and A. Xiao. “Faster algorithms for the geometric transportation problem.” In Leibniz International Proceedings in Informatics, LIPIcs, 77:71–716, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.7.
Agarwal PK, Fox K, Panigrahi D, Varadarajan KR, Xiao A. Faster algorithms for the geometric transportation problem. In: Leibniz International Proceedings in Informatics, LIPIcs. 2017. p. 71–716.
Agarwal, P. K., et al. “Faster algorithms for the geometric transportation problem.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 77, 2017, pp. 71–716. Scopus, doi:10.4230/LIPIcs.SoCG.2017.7.
Agarwal PK, Fox K, Panigrahi D, Varadarajan KR, Xiao A. Faster algorithms for the geometric transportation problem. Leibniz International Proceedings in Informatics, LIPIcs. 2017. p. 71–716.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959770385

Publication Date

June 1, 2017

Volume

77

Start / End Page

71 / 716

Related Subject Headings

  • 46 Information and computing sciences