Personal tools
You are here: Home CG seminar Spring 2017 Efficient Algorithms for Computing Transportation Maps
« March 2017 »
Log in

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


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
tion algorithm,
(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.
Document Actions