Algorithms Seminar
NearLinear Time Approximate Transportation
Speaker:  Allen Xiao

Date: 
Thursday, January 26, 2017 
Time: 
12:00pm  1:00pm 
Location: 
D344 LSRC, Duke 


Abstract
In the geometric transportation problem, we are given a set of n red and
blue points in R^d. Each red point has an integer supply and each blue
point an integer demand, such that the sum of supply and sum of demand
are both equal to U. A transportation is an assignment of the supply
units to demand, with the cost per unit of an assignment from point r to
point b is equal to r  b. The geometric transportation problem asks
to find the minimum cost transportation. Transportation is a
generalization of minimum cost matching, but known results are
substantially weaker  e.g. there are no known nearlinear time
O(1)approximations, and until recently no subquadratic algorithms at
all.
We describe three new results for the geometric transportation problem:
a nearquadratic time exact algorithm, a weaklypolynomial
(1+\epsilon)approximation in O(n^{3/2} polylog(n) log(U)) time, and a
randomized O(n^{1+\epsilon})time O(log^2(1/\epsilon))approximation.
This talk will present the first two at a high level and focus on the
last. This is joint work with Pankaj Agarwal, Kasturi Varadarjan,
Debmalya Panigrahi, and Kyle Fox.
Biography
Allen Xiao is a thirdyear PhD student at Duke, advised by Pankaj
Agarwal. His research interests are in graph algorithms in geometric
settings.