Economical Caching
Economical Caching
复制标题
DOI：
10.1145/2493246.2493247
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Matthias Englert;Heiko Röglin;J. Spönemann;Berthold Vöcking
中科院分区：
文献类型：
--
作者：
Matthias Englert;Heiko Röglin;J. Spönemann;Berthold Vöcking
我们研究了在竞争分析中不可预测地变化价格的环境中缓冲区和存储的管理。在经济缓存问题中，存在具有一定容量的存储。对于每个时间步，在线算法都会给出区间[1，α]的价格、消费量以及可能的购买限额。在线算法必须决定从某种商品购买的数量，知道参数α，但不知道价格在未来如何演变。该算法可以在最多买入限额内买入。如果它的购买量超过当前的消费量，那么多余的部分就被储存在存储器中;否则，消费量和购买量之间的差距就必须从存储器中取出。目标是使总成本最小化。有趣的激励应用是，例如，具有不同服务类别的移动的设备上的流缓存、微型混合动力汽车中的电池管理以及资源的有效购买。首先，我们考虑简单但自然的一类算法，可以非正式地描述为无记忆的。我们表明，这些算法不能实现低于α的竞争比。然后，我们提出了一个更复杂的确定性算法，实现了竞争比，其中W表示Lambert W函数。我们证明了该算法是最优的，即使是随机在线算法也不能达到更好的竞争比。另一方面，我们展示了如何实现一个恒定的竞争比，如果存储容量的在线算法超过存储容量的最佳离线算法的log α的一个因素。
We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain capacity. For each time step, an online algorithm is given a price from the interval [1, α], a consumption, and possibly a buying limit. The online algorithm has to decide the amount to purchase from some commodity, knowing the parameter α but without knowing how the price evolves in the future. The algorithm can purchase at most the buying limit. If it purchases more than the current consumption, then the excess is stored in the storage; otherwise, the gap between consumption and purchase must be taken from the storage. The goal is to minimize the total cost. Interesting motivating applications are, for example, stream caching on mobile devices with different classes of service, battery management in micro hybrid cars, and the efficient purchase of resources. First we consider the simple but natural class of algorithms that can informally be described as memoryless. We show that these algorithms cannot achieve a competitive ratio below √α. Then we present a more sophisticated deterministic algorithm achieving a competitive ratio of where W denotes the Lambert W function. We prove that this algorithm is optimal and that not even randomized online algorithms can achieve a better competitive ratio. On the other hand, we show how to achieve a constant competitive ratio if the storage capacity of the online algorithm exceeds the storage capacity of an optimal offline algorithm by a factor of log α.