Math @ Duke

Publications [#235546] of Pankaj K. Agarwal
Papers Published
 Sharathkumar, R; Agarwal, PK, Algorithms for the transportation problem in geometric settings,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2012),
pp. 306317
(last updated on 2018/03/20)
Abstract: For A, B ⊂ ℝ d, A + B = n, let a ∈ A have a demand d a ∈ ℤ + and b ∈ B have a supply s b ∈ ℤ +, Σ a∈A d a = Σ b∈B s b = U and let d(·,·) be a distance function. Suppose the diameter of A ∪ B is Δ under d(·,·), and ε > 0 is a parameter. We present an algorithm that in O((n√U log 2 n + U log U)Φ(n)log(ΔU/ε)) time computes a solution to the transportation problem on A, B which is within an additive error ε from the optimal solution. Here Φ(n) is the query and update time of a dynamic weighted nearest neighbor data structure under distance function d(·,·). Note that the (1/ε) appears only in the log term. As among various consequences we obtain, • For A, B ⊂ ℝ d and for the case where d(·,·) is a metric, an εapproximation algorithm for the transportation problem in O((n√U log 2 n + U log U)Φ(n)log(ΔU/ε)) time. • For A, B ⊂ [Δ] d and the L 1 and L ∞, distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O(n 3/2 log d+O(1) n log Δ) time. • For A, B ⊂ [Δ] 2 and RMS distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O(n 3/2+δ log Δ) time, for an arbitrarily small constant δ > 0. For point sets, A, B ⊂ [Δ] d, for the L p norm and for O < α,β < 1, we present a randomized dynamic data structure that maintains a partial solution to the transportation problem under insertions and deletions of points in which at least (1  α) U of the demands are satisfied and whose cost is within (1 + β) of that of the optimal (complete) solution to the transportation problem with high probability. The insertion, deletion and update times are O(poly(log(nΔ)/αβ)), provided U = n O(1). Copyright © SIAM.


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

