Paper Info
Title
Verified Analysis of List Update Algorithms.
Abstract
This paper presents a machine-verified analysis of a number of classical algorithms for the list update problem: 2-competitiveness of move-to-front, the lower bound of 2 for the competitiveness of deterministic list update algorithms and 1.6-competitiveness of the randomized COMB algorithm, the best randomized list update algorithm known to date. The analysis is verified with help of the theorem prover Isabelle; some low-level proofs could be automated.
Year
Venue
Field
2016
FSTTCS
List update problem,Computer science,Upper and lower bounds,Automated theorem proving,Algorithm,Theoretical computer science,Probabilistic analysis of algorithms,Mathematical proof,Self-organizing list,Randomized algorithms as zero-sum games
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Maximilian Haslbeck123.09
Tobias Nipkow23056232.28