Algorithms Seminar

An Input-Sensitive Online Algorithm for the Minimum Metric Bipartite

Speaker:Sharath Raghvendra
Date: Thursday, October 26, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


In the online minimum-metric bipartite matching problem, we are given a set S of server locations. The locations of requests are revealed one at a time and when a request is revealed, 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. In this talk, I will present a fine-grained and input sensitive analysis of an online algorithm (called the (Robust-Matching) RM-Algorithm) for this problem. I will show that, in the adversarial model, for any set of servers S, the competitive ratio of the RM-Algorithm is O(mu(S)log^2 n) where mu(S) is the maximum ratio of the traveling salesman tour to the diameter over all subsets of S. It is straight-forward to see that the optimal competitive ratio for any online algorithm which is optimized for S is \Omega(\mu(S)). In this sense, the RM-Algorithm is near-optimal for every input set of servers. When S is a set of points on a line, \mu(S)=2 and so the competitive ratio of RM-Algorithm is O(log^2 n). Despite several efforts, the best previous result for the line metric is only an n^{0.59}-competitive algorithm when S are points in a d-dimensional space, \mu(S)=n^{1-1/d} and the competitive ratio of RM-Algorithm is O(n^{1-1/d}log^2 n). This is joint work with Krati Nayyar and appears in FOCS'17.


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 exact and approximation algorithms for problems in computational geometry, topology and graph theory.