- Info

#
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

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.