Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#329182] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Fox, K; Panigrahi, D; Varadarajan, KR; Xiao, A, Faster algorithms for the geometric transportation problem, LIPIcs, vol. 77 (June, 2017), pp. 71-716, ISBN 9783959770385 [doi]
    (last updated on 2017/12/13)

    © Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Let R, B C R d 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 L p 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 L p metric: • For any constant ϵ > 0, an O(n 1+ϵ ) expected time randomized algorithm that returns a transportation map with expected cost O(log 2 (1/ϵ)) times the optimal cost. • For any ϵ > 0, a (1 + ϵ)-approximation in O(n 3/2 ϵ -d polylog(U) polylog(n)) time, where U = max p∈Rcup;B λ (p). •An exact strongly polynomial O(n 2 polylogn) time algorithm, for d = 2.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320