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 real-time 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 minimum-cost matching of S and R. The algorithm that I present is based on a variant of the offline primal-dual 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 well-known 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.