Theory Seminar: Billy Jin, "Advice-Augmented Algorithms for Online Matching and Resource Allocation"

Event Type

Seminar/Symposium

Sponsor

Michael A. Forbes

Location

Siebel 3401

Date

Apr 7, 2025   11:00 am  

Speaker

Billy Jin

Originating Calendar

Siebel School Speakers Calendar

Theory Seminar: Please join us on April 7th at 11 am in Siebel 3401 where Billy Jin, will give a talk, “Advice-Augmented Algorithms for Online Matching and Resource Allocation”. Please see the abstract and biography below:

Abstract:

       Real life problems are full of uncertainty.  How we handle it is important, since it affects the design and performance of algorithms.  Often, the uncertainty is assumed to follow some known distribution, but in practice the estimate of the distribution may or may not be accurate.  At other times, the uncertainty is assumed to be adversarial, but this can be too pessimistic for most real life instances.

       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.

Bio:

       Billy will join Purdue University this summer as an Assistant Professor in the Daniels School of Business.  He is currently a postdoctoral researcher at Chicago Booth, working with Baris Ata.  He obtained his PhD in Operations Research at Cornell University, where he was advised by David Williamson.  His research interests lie in the union of online decision-making, stochastic optimization, and approximation algorithms.  His research has been recognized with several awards, including an NSERC graduate fellowship, the 2023 Student Paper Prize awarded by the INFORMS Decision Analysis Society, and runner-up in the 2023 Student Paper Prize awarded by the INFORMS Optimization Society.