Algorithms for the Transportation Problem in Geometric Settings
R. Sharathkumar, Pankaj K. Agarwal · 2012
For A, B ⊂ R d, |A | + |B | = n, let a ∈ A have a demand da ∈ Z + and b ∈ B have a supply sb ∈ Z + ∑ a∈A da b∈B sb = 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 ⊂ R 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 L1 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 Lp norm and for 0 < α, β < 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). 1