| Article ID: | iaor20117035 |
| Volume: | 36 |
| Issue: | 3 |
| Start Page Number: | 209 |
| End Page Number: | 224 |
| Publication Date: | Jul 2003 |
| Journal: | Algorithmica |
| Authors: | Kenyon , Karlin , Randall |
| Keywords: | ski rental problem |
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.