caa a22 4500 445804319 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-009-9366-4 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9366-4 Knowledge State Algorithms [Elektronische Daten] [Wolfgang Bein, Lawrence Larmore, John Noga, Rüdiger Reischuk] 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. Springer Science+Business Media, LLC, 2009 Competitive analysis nationallicence Online algorithms nationallicence Task systems nationallicence Randomization nationallicence Paging nationallicence Server problem nationallicence Bein Wolfgang Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada, 89154, Las Vegas, NV, USA aut Larmore Lawrence Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada, 89154, Las Vegas, NV, USA aut Noga John Department of Computer Science, California State University, 91330, Northridge, CA, USA aut Reischuk Rüdiger Institut für Theoretische Informatik, Universität Lübeck, Ratzeburger Allee 160, 23538, Lübeck, Germany aut Algorithmica Springer-Verlag 60/3(2011-07-01), 653-678 0178-4617 60:3<653 2011 60 453 https://doi.org/10.1007/s00453-009-9366-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9366-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bein Wolfgang Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada, 89154, Las Vegas, NV, USA aut NATIONALLICENCE 700 1- Larmore Lawrence Center for the Advanced Study of Algorithms, School of Computer Science, University of Nevada, 89154, Las Vegas, NV, USA aut NATIONALLICENCE 700 1- Noga John Department of Computer Science, California State University, 91330, Northridge, CA, USA aut NATIONALLICENCE 700 1- Reischuk Rüdiger Institut für Theoretische Informatik, Universität Lübeck, Ratzeburger Allee 160, 23538, Lübeck, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 653-678 0178-4617 60:3<653 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer