Algorithms Seminar

Near-Linear 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 near-linear time O(1)-approximations, and until recently no sub-quadratic algorithms at all. We describe three new results for the geometric transportation problem: a near-quadratic time exact algorithm, a weakly-polynomial (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 third-year PhD student at Duke, advised by Pankaj Agarwal. His research interests are in graph algorithms in geometric settings.