Online Aggregation Problems with Delay

Speaker

William Umboh January 12, 2024.

Abstract

In the traditional model of online algorithms, requests arrive over time and each request has to be served immediately by the algorithm on arrival. Recently, there has been a lot of interest in online problems with delay where requests can be delayed at some cost and served together in batches. In particular, the main algorithmic challenge is in balancing the delay cost and the economies-of-scale of serving requests in batches. In this talk, we will survey recent advances in a rich subclass of online problems with delay that generalize classic online problems such as TCP Acknowledgement.