Forgot your password?
Efficient Algorithms for Computing Transportation Maps
Wednesday, February 8th, 2017 16:10
Schreiber 309
Efficient Algorithms for Computing Transportation Maps
Pankaj K. Agarwal, Duke University
Abstract:
We introduce the notion of depth with respect to a finite family F of convex sets in R^d that generalizes the well-studied Tukey depth. Specifically, we say that a point p has Given a set of n red and blue points in R^d, each red point with a supply value and each blue point with a demand value such that the sum of supply and the sum of demand are both equal to U. A transportation map is an assignment of the supply units to demand so that the supply and demand constraints are satisfied; the cost per unit of an assignment from point r to point b is equal to ||r - b||. The transportation-map problem asks to compute a minimum-cost transportation map. This problem is a generalization of the minimum-cost Euclidean matching between two points sets, but known results are substantially weaker -- there are no known near-linear time O(1)-approximations, and in fact no sub-quadratic algorithms for U > n^2.
We describe three new results:
(i) a randomized O(n^{1+\epsilon})-time O(log^2(1/\epsilon))-approxima(ii) O(n^{3/2} polylog(n) log(U)) time (1+\epsilon)-approximation algorithm, assuming the supply/demand of each point is an integer, and
(iii) an O(n^2 polylog(n))-time exact algorithm for d=2
This is joint work with Kasturi Varadarajan, Debmalya Panigrahi, and Kyle Fox.
