Algorithms Seminar
An InputSensitive Online Algorithm for the Minimum Metric Bipartite
Speaker:  Sharath Raghvendra

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


Abstract
In the online minimummetric 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 minimumcost matching of S and R.
In this talk, I will present a finegrained and input sensitive analysis of an online algorithm (called the (RobustMatching) RMAlgorithm) for this problem. I will show that, in the adversarial model, for any set of servers S, the competitive ratio of the RMAlgorithm 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 straightforward to see that the optimal competitive ratio for any online algorithm which is optimized for S is \Omega(\mu(S)). In this sense, the RMAlgorithm is nearoptimal 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 RMAlgorithm 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 ddimensional space, \mu(S)=n^{11/d} and the competitive ratio of RMAlgorithm is O(n^{11/d}log^2 n).
This is joint work with Krati Nayyar and appears in FOCS'17.
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 exact and approximation algorithms for problems in computational geometry, topology and graph theory.