Dynamic TCP Acknowledgment and Other Stories about e/(e - 1) |
| |
| Authors: | Karlin Kenyon Randall |
| |
| Affiliation: | (1) Department of Computer Science and Engineering, University of Washington, Seattle, WA, USA. karlin@cs.washington.edu., US;(2) LIX, Ecole Polytechnique, 91128 Palaiseau, France. kenyon@lix.polytechnique.fr., FR;(3) College of Computing and School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA. randall@cc.gatech.edu., US |
| |
| Abstract: | Abstract. 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. |
| |
| Keywords: | . TCP acknowledgment Online algorithms Ski-rental Basis inputs. |
| 本文献已被 SpringerLink 等数据库收录！ |
|
