View PDF HTML (experimental)

Abstract:In a seminal work, Dooly, Goldman, and Scott (STOC 1998; JACM 2001) introduced the classic Online TCP Acknowledgment} problem: 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. They showed that a natural greedy algorithm, which acknowledges when the delay of pending packets equals the acknowledgment cost, is $2$-competitive.
Online TCP Acknowledgment is the canonical online problem with delay, capturing the fundamental tradeoff between reducing service cost through batching and the delay incurred by pending requests. Prior work has largely focused on richer service-cost models, e.g., Multi-Level Aggregation. However, besides the work of Albers and Bals (SODA 2003), which studies maximum delay and similar objectives, not much is known beyond the sum of delay costs of requests.
In this work, we study Online TCP Acknowledgment under two generalized delay-cost models. In the batch-aware model, each batch incurs a delay cost that depends on the packet delays within that batch. For the max-over-batches objective, we show that greedy remains $2$-competitive. For the sum-over-batches objective, the picture changes sharply: greedy is $\Omega(n)$-competitive, and the optimal deterministic competitive ratio is $\Theta(\log n)$. Our upper bounds only require the batch delay function to be monotone.
In the batch-oblivious model, the delay cost is a function of the global packet-delay vector. We show that greedy is $2$-competitive for continuous submodular delay costs, and more generally under a weaker zero-coordinate diminishing-marginals condition. This yields $2$-competitive algorithms for ordered norms. Using the submodular-norm approximation of Patton, Russo, and Singla, we also obtain an $O(\log n)$-competitive algorithm for arbitrary symmetric norms.

Submission history

From: Seeun William Umboh [view email]
[v1] Wed, 15 Apr 2026 02:56:51 UTC (30 KB)
[v2] Tue, 14 Jul 2026 05:01:43 UTC (35 KB)