Math @ Duke

Publications [#329182] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Fox, K; Panigrahi, D; Varadarajan, KR; Xiao, A, Faster algorithms for the geometric transportation problem,
Leibniz International Proceedings in Informatics, Lipics, vol. 77
(June, 2017),
pp. 71716, ISBN 9783959770385 [doi]
(last updated on 2018/12/18)
Abstract: © Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Let R, B C Rdfor 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 Lpdistance. 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 Lpmetric: • 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ϵdpolylog(U) polylog(n)) time, where U = maxp∈Rcup;Bλ (p). •An exact strongly polynomial O(n2polylogn) time algorithm, for d = 2.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

