INFORMS STUDENT CHAPTER Seminar
Time: 11:00am-12:00pm Nov 11
Zoom information: https://virginiatech.zoom.us/my/isemain
Speaker: Sharath Raghvendra, Department of Computer Science, Virginia Tech
Abstract: In the online minimum-metric bipartite matching (OMBM) problem, we are given a set S of server locations. The locations of requests (given by the set R) 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 an online algorithm (called the (Robust-Matching) RM-Algorithm) for this problem and show that it gives near optimal performance in the adversarial and random arrival models and for special metrics such as the line metric. The analysis for all of these cases is based on the dynamics of a primal-dual method used within the RM-algorithm. I will conclude the talk by discussing some open questions pertaining to the OMBM and the closely related k-server problems.
Part of this talk is based on joint work with students Krati Nayyar and Rachita Sowle. Results presented here appear in APPROX 2016, FOCS 2017, SoCG 2018 and SWAT 2022.
Bio: Sharath Raghvendra is an Associate Professor in the Department of
Computer Science at Virginia Tech. Before joining Virginia Tech, he
spent two years (2012-2014) 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. His research
interests focus on designing provable algorithms for optimization
including problems related to matching and optimal transport amongst
other areas. His work has been published in top tier conferences and
journals in theoretical computer science, such as Journal of the ACM,
ACM SIAM Symposium on Discrete Algorithms (SODA), International
Symposium on Computational Geometry (SoCG), ACM Symposium on Theory of
Computing (STOC) and IEEE Symposium on Foundations of Computer Science