✦ LIBER ✦

A faster off-line algorithm for the TCP acknowledgement problem

✍ Scribed by John Noga; Steve Seiden; Gerhard J. Woeginger

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 48 KB
Volume: 81
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00199-5

No coin nor oath required. For personal study only.

✦ Synopsis

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(n 2 ) 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).

📜 SIMILAR VOLUMES

Off-line algorithms for the list update

Off-line algorithms for the list update problem

✍ Nick Reingold; Jeffery Westbrook 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 637 KB

Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum algorithms are given; these lead to optimum algorithm which runs in time 02"( n -1) !m, where n is the

A faster optimal algorithm for the measu

A faster optimal algorithm for the measure problem

✍ Stephan Olariu; Zhaofang Wen; Weixiong Zhang 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 238 KB

A Faster Algorithm for the Inverse Spann

A Faster Algorithm for the Inverse Spanning Tree Problem

✍ Ravindra K. Ahuja; James B. Orlin 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 149 KB

In this paper, we consider the inverse spanning tree problem. Given an undi-0 Ž 0 0 . rected graph G s N , A with n nodes, m arcs, an arc cost vector c, and a spanning tree T 0 , the inverse spanning tree problem is to perturb the arc cost vector c to a vector d so that T 0 is a minimum spanning tre

A faster algorithm for the two-center de

A faster algorithm for the two-center decision problem

✍ John Hershberger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 569 KB

A faster algorithm for the maximum weigh

A faster algorithm for the maximum weighted tardiness problem

✍ Malcolm C. Fields; Greg N. Frederickson 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 503 KB

A faster polynomial algorithm for the un

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

✍ Ulrich Brenner 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 320 KB

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk 2 (log n + k log k)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomialtime algorithm