Knowledge State Algorithms: Randomization with Limited Information

Details Knowledge State Algorithms: Randomization with Limited Information Knowledge State Algorithms: Randomization with Limited Information

2007-01-23

arxiv.org/abs/cs/0701142v1

Computer Science

Data Structures and Algorithms

17 pages, 2 figures

Scientific paper

We introduce the concept of knowledge states; many well-known algorithms can be viewed as knowledge state algorithms. The knowledge state approach can be used to to construct competitive randomized online algorithms and study the tradeoff between competitiveness and memory. A knowledge state simply states conditional obligations of an adversary, by fixing a work function, and gives a distribution for the algorithm. 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 then uses randomization to select one of those subsequents to be the new knowledge state. We apply the method to the paging problem. We present optimally competitive algorithm for paging for the cases where the cache sizes are k=2 and k=3. These algorithms use only a very limited number of bookmarks.

Affiliated with

Also associated with

No associations

Rating

Knowledge State Algorithms: Randomization with Limited Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Knowledge State Algorithms: Randomization with Limited Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Knowledge State Algorithms: Randomization with Limited Information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-205779