## Dynamic TCP acknowledgment and other stories about $$e/(e-1)$$.(English)Zbl 1045.68155

Summary: We present the first optimal randomized online algorithms for the TCP acknowledgment problem and the Bahncard problem. 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.

### MSC:

 68W05 Nonnumerical algorithms

### Keywords:

TCP acknowledgment; Online algorithms; Ski-rental; Basis inputs
Full Text: