Cai, Zhao-Quan On-line algorithm of loose competitive caching. (Chinese. English summary) Zbl 1181.68314 J. Comput. Appl. 28, No. 10, 2604-2607 (2008). Summary: In response to a sequence of requests for files, where each file has a specified size and retrieval cost, the total size of each file in cache is maintained at some specified \(k\) so as to minimize the total retrieval cost. A simple deterministic on-line algorithm is proposed. In this algorithm, many well-known paging and weighted caching strategies are generalized, and the retrieval cost is either insignificant or at most a constant (independent of \(k\)) times the optimum value for most \(k\). This helps explain why competition ratios of many on-line paging algorithms have been typically observed to be constant in practice. MSC: 68W05 Nonnumerical algorithms Keywords:paging; caching; on-line algorithm; competitive analysis PDFBibTeX XMLCite \textit{Z.-Q. Cai}, J. Comput. Appl. 28, No. 10, 2604--2607 (2008; Zbl 1181.68314) Full Text: DOI