Algorithms Seminar
Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
Speaker:  Sharath Raghavendra

Date: 
Friday, April 22, 2016 
Time: 
12:00pm  1:00pm 
Location: 
North 311, Duke 


Abstract
Motivated by realtime logistics, I will present a deterministic algorithm for the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given a set S of server locations and a set R of request locations. The requests arrive one at a time and when it arrives, we must immediately and irrevocably match it to a ``free" server. The cost of matching a server to request is given by the distance between the two locations (which we assume satisfies triangle inequality). The objective of this problem is to come up with a matching of servers to requests which is competitive with respect to the minimumcost matching of S and R. The algorithm that I present is based on a variant of the offline primaldual method where the constraint for every edge is relaxed by a fixed multiplicative factor. Using the fact that the costs between locations satisfy triangle inequality, I will show that this deterministic algorithm simultaneously achieves optimal performances in two wellknown online models  the adversarial and the random arrival models.
Biography
Dr. Sharath Raghvendra is an Assistant Professor in the Department of Computer Science at Virginia Tech. Before joining Virginia Tech, he spent two years as a postdoctoral scholar at Stanford University. Dr. Raghvendra received his Ph.D from Duke University in 2012 where he won the Best Doctoral Dissertation Award. He is also the recipient of NSF CRII Award in 2014.
His research interests span design of algorithms for problems in algebraic topology, computational geometry and graph theory.