An O (log k )-competitive algorithm for generalized caching
An O (log k )-competitive algorithm for generalized caching
复制标题
用于广义缓存的 O (log k ) 竞争算法
DOI：
10.1137/1.9781611973099.133
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Adamaszek A
中科院分区：
文献类型：
--
作者：
Adamaszek A
在广义缓存问题中，我们有一组页面和一个大小为sizek的缓存。每个页面都有一个sizewp≥ 1，并有一个用于将页面加载到该高速缓存的获取成本cp。在任何时间点，存储在该高速缓存中的页大小之和都不能被重命名。输入由一系列页面请求组成。如果一个页面不存在于该高速缓存在它被请求的时候，它必须被加载到该高速缓存招致成本ofcp.我们给出了一个随机化O（logk）-竞争的在线算法的广义缓存问题，提高了以前的边界ofO（log 2k）的Bansal，Buchbinder，和Naor（STOC'08）。这个改进的界是渐近紧的，与已知的具有均匀权重和大小的经典问题的界具有相同的阶。我们遵循Bansal等人提出的基于LP的技术，我们的主要贡献是改进和稍微简化了在线舍入分数解的方法。
In the generalized caching problem, we have a set of pages and a cache of sizek. Each pagephas a sizewp≥ 1 and fetching costcpfor loading the page into the cache. At any point in time, the sum of the sizes of the pages stored in the cache cannot exceedk. The input consists of a sequence of page requests. If a page is not present in the cache at the time it is requested, it has to be loaded into the cache incurring a cost ofcp.We give a randomizedO(logk)-competitive online algorithm for the generalized caching problem, improving the previous bound ofO(log2k) by Bansal, Buchbinder, and Naor (STOC'08). This improved bound is asymptotically tight and of the same order as the known bounds for the classic problem with uniform weights and sizes. We follow the LP based techniques proposed Bansal et al. and our main contribution are improved and slightly simplified methods for rounding fractional solutions online.