Abstract
We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k)-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O(log(k/(k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k.
Our solution is based on a two-step approach. We first obtain an O(log k)-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O(log N)-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves.
- Achlioptas, D., Chrobak, M., and Noga, J. 2000. Competitive analysis of randomized paging algorithms. Theoret. Computer Science 234, 1--2, 203--218. Google ScholarDigital Library
- Adamaszek, A., Czumaj, A., Englert, M., and Räcke, H. 2012. An O(log k)-competitive algorithm for generalized caching. In SODA. 1681--1689. Google ScholarDigital Library
- Albers, S. 2003. Online algorithms: A survey. Math. Prog. 97, 3--26.Google ScholarCross Ref
- Bansal, N., Buchbinder, N., Madry, A., and Naor, J. 2011. A polylogarithmic-competitive algorithm for the k-server problem. In Proceedings of the Symposium on Foundations of Computer Science. 267--276. Google ScholarDigital Library
- Bansal, N., Buchbinder, N., and Naor, J. S. 2008. Randomized competitive algorithms for generalized caching. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 235--244. Google ScholarDigital Library
- Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J. S., and Schieber, B. 2001. A unified approach to approximating resource allocation and scheduling. J. ACM 48, 5, 1069--1090. Google ScholarDigital Library
- Bartal, Y., Blum, A., Burch, C., and Tomkins, A. 1997. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 711--719. Google ScholarDigital Library
- Blum, A., Furst, M., and Tomkins, A. 1996. What to do with your free time: Algorithms for infrequent requests and randomized weighted caching. Manuscript. (www.cs.cmu.edu)Google Scholar
- Borodin, A. and El-Yaniv, R. 1998. Online computation and competitive analysis. Cambridge University Press. Google ScholarDigital Library
- Borodin, A., Linial, N., and Saks, M. E. 1992. An optimal on-line algorithm for metrical task system. J. ACM 39, 4, 745--763. Google ScholarDigital Library
- Buchbinder, N., Jain, K., and Naor, J. S. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proceedings of the 15th Annual European Symposium. 253--264. Google ScholarDigital Library
- Buchbinder, N. and Naor, J. 2005. Online primal-dual algorithms for covering and packing problems. In Proceedings of the 13th Annual European Symposium on Algorithms. 689--701. Google ScholarDigital Library
- Buchbinder, N. and Naor, J. 2006. Fair online load balancing. In Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures. 291--298. Google ScholarDigital Library
- Buchbinder, N. and Naor, J. 2009. The design of competitive online algorithms via a primal-dual approach. Found. Trends Theoret. Comput. Sci. 3, 2--3, 93--263. Google ScholarDigital Library
- Chrobak, M., Karloff, H., Payne, T., and Vishwanathan, S. 1991. New results on server problems. SIAM J. Disc. Math 4, 2, 172--181. Google ScholarDigital Library
- Chrobak, M. and Larmore, L. L. 1991. An optimal on-line algorithm for k-servers on trees. SIAM J. Comput. 20, 1, 144--148. Google ScholarDigital Library
- Cohen, E. and Kaplan, H. 1999. LP-based analysis of greedy-dual-size. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. 879--880. Google ScholarDigital Library
- Coté, A., Meyerson, A., and Poplawski, L. 2008. Randomized k-server on hierarchical binary trees. In STOC’08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 227--234. Google ScholarDigital Library
- Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., and Young, N. E. 1991. Competitive paging algorithms. J. Algorithms 1, 4, 685--699. Google ScholarDigital Library
- Fiat, A. and Mendel, M. 2003. Better algorithms for unfair metrical task systems and applications. SIAM J. Comput. 32, 6, 1403--1422. Google ScholarDigital Library
- Fiat, A., Rabani, Y., and Ravid, Y. 1994. Competitive k-server algorithms. J. Comput. Syst. Sci. 48, 3, 410--428. Google ScholarDigital Library
- Irani, S. 1997. Page replacement with multi-size pages and applications to web caching. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 701--710. Google ScholarDigital Library
- Irani, S. 2002. Randomized weighted caching with two page weights. Algorithmica 32, 4, 624--640.Google ScholarDigital Library
- Koutsoupias, E. and Papadimitriou, C. H. 1995. On the k-server conjecture. J. ACM 42, 5, 971--983. Google ScholarDigital Library
- Manasse, M. S., McGeoch, L. A., and Sleator, D. D. 1990. Competitive algorithms for server problems. J. Algorithms 11, 2, 208--230. Google ScholarDigital Library
- McGeoch, L. A. and Sleator, D. D. 1991. A strongly competitive randomized paging algorithm. Algorithmica 6, 6, 816--825.Google ScholarDigital Library
- Sleator, D. D. and Tarjan, R. E. 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28, 2, 202--208. Google ScholarDigital Library
- Young, N. 1991. On-line caching as cache size varies. In SODA’91: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. 241--250. Google ScholarDigital Library
- Young, N. E. 1994. The k-server dual and loose competitiveness for paging. Algorithmica 11, 6, 525--541.Google ScholarDigital Library
Index Terms
- A Primal-Dual Randomized Algorithm for Weighted Paging
Recommendations
Efficient Online Weighted Multi-Level Paging
SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and ArchitecturesWe study the writeback-aware caching problem, a variant of classic paging where paging requests that modify data and requests that leave data intact are treated differently. We give an O(łog^2 k) competitive randomized algorithm, answering an open ...
Randomized competitive algorithms for generalized caching
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingWe consider online algorithms for the generalized caching problem. Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages ...
A Primal-Dual Randomized Algorithm for Weighted Paging
FOCS '07: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer ScienceIn the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized {\rm O}(\log k)-competitive online algorithm for the weighted paging problem, where k is the cache size. This is the first randomized o(...
Comments