Abstract
We introduce the novel concept of knowledge states. The knowledge state approach can be used to construct competitive randomized online algorithms and study the trade-off between competitiveness and memory. Many well-known algorithms can be viewed as knowledge state algorithms. A knowledge state consists of a distribution of states for the algorithm, together with a work function which approximates the conditional obligations of the adversary. When a knowledge state algorithm receives a request, it then calculates one or more “subsequent” knowledge states, together with a probability of transition to each. The algorithm uses randomization to select one of those subsequents to be the new knowledge state. We apply this method to randomized k-paging. The optimal minimum competitiveness of any randomized online algorithm for the k-paging problem is the kth harmonic number, \(H_{k}=\sum^{k}_{i=1}\frac{1}{i}\). Existing algorithms which achieve that optimal competitiveness must keep bookmarks, i.e., memory of the names of pages not in the cache. An H k -competitive randomized algorithm for that problem which uses O(k) bookmarks is presented, settling an open question by Borodin and El-Yaniv. In the special cases where k=2 and k=3, solutions are given using only one and two bookmarks, respectively.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theor. Comput. Sci. 234, 203–218 (2000)
Bartal, Y., Chrobak, M., Larmore, L.L.: A randomized algorithm for two servers on the line. In: Proceedings 6th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, pp. 247–258. Springer, Berlin (1998)
Bartal, Y., Chrobak, M., Larmore, L.L.: A randomized algorithm for two servers on the line. Inf. Comput. 158, 53–69 (2000)
Bein, W., Fleischer, R., Larmore, L.L.: Limited bookmark randomized online algorithms for the paging problem. Inf. Process. Lett. 76, 155–162 (2000)
Bein, W., Larmore, L.L.: Trackless online algorithms for the server problem. Inf. Process. Lett. 74, 73–79 (2000)
Bein, W., Larmore, L.L.: Trackless and limited bookmark algorithms for paging. SIGACT News 35, 40–49 (2004)
Bein, W., Larmore, L.L., Reischuk, R.: Knowledge states for the caching problem in shared memory multiprocessor systems. Int. J. Found. Comput. Sci. 40(1), 167–183 (2009)
Bein, W.W., Iwama, K., Kawahara, J., Larmore, L.L., Oravec, J.A.: A randomized algorithm for two servers in cross polytope spaces. In: Proceedings of 5th Workshop on Approximation and Online Algorithms (WAOA), Eilat, Israel, October 11–12, 2007. Lecture Notes in Computer Science, vol. 4927, pp. 246–259. Springer, Berlin (2008)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Chrobak, M., Koutsoupias, E., Noga, J.: More on randomized on-line algorithms for caching. Theor. Comput. Sci. 290, 1997–2008 (2003)
Chrobak, M., Larmore, L.L.: The server problem and on-line games. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 7, pp. 11–64 (1992)
Coppersmith, D., Doyle, P.G., Raghavan, P., Snir, M.: Random walks on weighted graphs and applications to online algorithms. In: Proceedings 22nd Symposium on Theory of Computing (STOC), pp. 369–378. ACM, New York (1990)
Fiat, A., Karp, R., Luby, M., McGeoch, L.A., Sleator, D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12, 685–699 (1991)
Koutsoupias, E., Papadimitriou, C.: Beyond competitive analysis. In: Proceedings 35th Symposium on Foundations of Computer Science (FOCS), pp. 394–400. IEEE, New York (1994)
Koutsoupias, E., Papadimitriou, C.: Beyond competitive analysis. SIAM J. Comput. 30, 300–317 (2000)
Schläfli, L.: Theorie der vielfachen Kontinuität. Birkhäuser, Basel (1857)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of W. Bein supported by NSF grant CCR-0312093.
Research of L.L. Larmore supported by NSF grant CCR-0312093.
Rights and permissions
About this article
Cite this article
Bein, W., Larmore, L.L., Noga, J. et al. Knowledge State Algorithms. Algorithmica 60, 653–678 (2011). https://doi.org/10.1007/s00453-009-9366-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-009-9366-4