Algorithms Seminar

Approximation Algorithms for Geometric Transportation

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


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 minimum-cost matching problem is a special case when all supplies and demands are 1. On geometric graphs, near-linear time approximation algorithms are known for minimum-cost matching. However, near-linear 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 well-separated pair decomposition and relies on a recent min-cost max-flow solver. We explain some unsuccessful attempts at generalizing the near-linear matching algorithms to the transportation problem.


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.