## 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.

## Published In

Leibniz International Proceedings in Informatics, LIPIcs

1868-8969

June 1, 2017

77

## Start / End Page

71 / 716

• 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

1868-8969

June 1, 2017

77

71 / 716