Online Aggregation Problems with Delay


William Umboh January 12, 2024.


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.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • Redundancy and Resilience in Distributed Optimization
  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • Derandomization from Time-Space Tradeoffs
  • Algorithms and Barriers for Fast Matrix Multiplication