Algorithms Seminar
Approximation Algorithms for Geometric Transportation
Speaker:  Allen Xiao

Date: 
Thursday, October 6, 2016 
Time: 
12:00pm  1:00pm 
Location: 
D344 LSRC, Duke 


Abstract
Given a weighted bipartite graph with n vertices, integer "supplies" on vertices of one side and "demands" on the other, the transportation problem is to find a mapping of supplies to demands with minimum weight. The minimumcost matching problem is a special case when all supplies and demands are 1. On geometric graphs, nearlinear time approximation algorithms are known for minimumcost matching. However, nearlinear approximation algorithms for the geometric transportation have remained elusive.
We present a new ~O(n^{3/2} log U) algorithm, where U is the maximum supply/demand. This algorithm uses wellseparated pair decomposition and relies on a recent mincost maxflow solver. We explain some unsuccessful attempts at generalizing the nearlinear matching algorithms to the transportation problem.
Biography
Allen Xiao is a third year Ph.D. student at Duke University doing research in computational geometry with Pankaj Agarwal. Before coming to Duke, he was a student at the University of California, Berkeley.