×

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
PDF BibTeX XML Cite
Full Text: DOI