Dynamic TCP acknowledgment and other stories about e/(e-1)
We present the first optimal randomized online algorithms for the TCP acknowledgment problem [3] and the Bahncard problem [5]. These problems are well known to be generalizations of the classical online ski-rental problem, however, they appeared to be harder. In this paper we demonstrate that a number of online algorithms which have optimal competitive ratios of e/(e-1), including these, are fundamentally no more complex than ski rental. Our results also suggest a clear paradigm for solving ski-rental-like problems.
tcp acknowledgment online algorithms ski-rental basis inputs