×

On-line algorithm of loose competitive caching. (Chinese. English summary) Zbl 1181.68314

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
PDFBibTeX XMLCite
Full Text: DOI