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

(FOCS).