A faster off-line algorithm for the TCP acknowledgement problem

In a recent paper [Proceedings of STOC'98, 1998, pp. 389-398], Dooly, Goldm an and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Contr ol Protocol (TCP). Among other results, they give an O(n(2)) off-line algor ithm for computing the optimal way of acknowledging n packet arrivals and d epartures. In this brief note, we observe that there is a faster off-line algorithm fo r this problem with time complexity O(n). (C) 2002 Elsevier Science B.V All rights reserved.