Title: Bulldozers and Teleporters: Sketching Earth Mover Distance on Graph Metrics

Speaker: Dan Stubbs, UMass Amherst

Abstract: 

I will describe a small-space data stream algorithm for estimating the earth mover distance (defined as the weight of the min-weight matching) between two point sets in the case where the distance between two points is determined by a known graph metric. The earth mover distance is used in image processing and can be computed offline by a reduction to the maximum flow problem. The new data stream algorithm uses a combination of existing techniques for the problem on a line and a new construction that simulates cycles using disjoint lines of edges with "teleporters" between them. 

Work done in conjunction with Andrew McGregor.