Advice-Augmented Algorithms for Online Matching and Resource Allocation

Advice-Augmented Algorithms for Online Matching and Resource Allocation (via Zoom)

Abstract: Real life problems are full of uncertainty. How we handle it is important, since it affects the design and performance of algorithms. In theoretical computer science, the uncertainty is usually assumed to be adversarial, which can be too pessimistic for most real life instances. On the other hand, in operations research, the uncertainty is usually assumed to follow some known distribution, but in practice the estimate of the distribution may or may not be accurate.

Advice-augmented algorithms aim to bridge the gap between these two models. In this framework, the algorithm is given some advice or prediction (e.g. from historical data, forecasts, or expert advice), whose quality is unknown. We aim to design algorithms that perform well when the quality is high (consistency), yet remain robust in their performance even when the quality is low (robustness).

In this talk, I will introduce algorithms with advice, and present two of my works in this area. The first is on two-stage matching: We design an algorithm that attains the optimal tradeoff between consistency and robustness. The second is on Nash social welfare maximization in online resource allocation: We show that access to reasonable predictions gives an exponential improvement over the worst-case performance. Convex optimization plays a key role in both works.
Based on joint work with Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, Safwan Hossain, Will Ma, Evi Micha, and Nisarg Shah.

Bio: Billy Jin is a final-year PhD student in ORIE at Cornell University, advised by David Williamson. His research lies in the intersection of online decision-making, stochastic optimization, and approximation algorithms. Billy is a recipient of the NSERC graduate fellowship. He graduated from the University of Waterloo in 2018 with a B.Math in Combinatorics & Optimization and Computer Science, where he was the recipient of the Alumni Gold Medal.