A short proof of optimality for the MIN cache replacement algorithm

作     者：Van Roy, Benjamin 

作者机构：Stanford Univ Stanford CA 94305 USA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (Inf. Process. Lett.)

年 卷 期：2007年第102卷第2-3期

页      面：72-73页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：analysis of algorithms on-line algorithms caching paging 

摘      要：The MIN algorithm is an offline strategy for deciding which item to replace when writing a new item to a cache. Its optimality was first established by Mattson et al. [R.L. Mattson, ***, D.R. Slutz, I.L. Traiger, Evaluation techniques for storage hierarchies, IBM Systems Journal 9 (2) (1970) 78-117] through a lengthy analysis. We provide a short and elementary proof based on a dynamic programming argument. (c) 2006 Elsevier B.V. All rights reserved.