Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A new lower bound for the list update problem in the partial cost model
 Theoretical Computer Science268 (1):3-16,2001.Type:Article
Date Reviewed: May 8 2002

The optimal competitive ratio for the list update problem is between 1.5 and 1.6. For lists of up to four elements, an optimal update algorithm exists. In this paper, the authors determine the lower bound for lists of at least five elements. To that end, the authors use a game tree that is composed of an irregularly structured finite list update problem (FLUP) tree with regularly structured inversion converter (IC) trees appended to its leaves. The authors find that an expected strict competitive ratio for the simplest version of FLUP is at least 1.50084, with higher lower bounds for larger FLUPs. The tree has incomplete information: the adversary who generates requests has no knowledge about the online algorithm that grants the requests.

Reviewer:  Adam Drozdek Review #: CR125917 (0205-0276)
Bookmark and Share
 
Lists, Stacks, And Queues (E.1 ... )
 
 
Trees (G.2.2 ... )
 
 
General (F.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Lists, Stacks, And Queues": Date
A priority queue for the all pairs shortest path problem
Moffat A., Takaoka T. Information Processing Letters 18(4): 189-193, 1984. Type: Article
Mar 1 1985
Amortized efficiency of list update and paging rules
Sleator D., Tarjan R. (ed) Communications of the ACM 28(2): 202-208, 1985. Type: Article
Nov 1 1985
Self-organizing search lists using probabilistic back-pointers
Hester J., Hirschberg D. Communications of the ACM 30(12): 1074-1079, 1987. Type: Article
Oct 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy