Online TCP Acknowledgment under General DelaysOberseminar Discrete Optimization

by William Umboh (University of Melbourne)

Monday Aug 17, 2026, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

We revisit the canonical online problem of TCP Acknowledgment (aka single-item lot sizing): a sequence of n packets arrives over time, and the objective is to minimize both the number of acknowledgments sent and the total delay experienced by the packets. It is well-known that greedy, which acknowledges when the delay of pending packets equals the acknowledgment cost, is 2‑competitive.

In this work, we consider more general delay cost models where the overall delay cost is not simply the sum of individual packet delays. We show that for some natural delay cost models, greedy is still 2-competitive. The most interesting setting is the batch-aware model where the algorithm pays a delay cost per acknowledgment that depends on the packet delays of the acknowledged packets. We show that greedy has linear competitive ratio, and give a logarithmic competitive algorithm. Finally, we show that the latter is tight via a surprising connection to the Parking Permit problem. 

This is joint work with Sujoy Bhore and Michał Pawłowski, and will appear in APPROX 2026. 

https://arxiv.org/abs/2604.13428

 

The Oberseminar takes place in the Seminarraum, 1st floor. Participants are invited to have coffee or tea in the lounge before.