A faster off-line algorithm for the TCP acknowledgement problem

John Noga, Steve Seiden, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)


In a recent paper [Proceedings of STOC’98, 1998, pp. 389–398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n2) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures.
In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n).
Original languageEnglish
Pages (from-to)71-73
JournalInformation processing letters
Issue number2
Publication statusPublished - 2002
Externally publishedYes


  • METIS-208607
  • Transmission Control Protocol
  • TCP acknowledgement
  • Netwerks
  • Dynamic Programming


Dive into the research topics of 'A faster off-line algorithm for the TCP acknowledgement problem'. Together they form a unique fingerprint.

Cite this