General caching is hard: even with small pages

DOI10.1007/s00453-016-0185-0zbMath1372.68084arXiv1506.07905OpenAlexW2594175587MaRDI QIDQ2408914

Lukáš Folwarczný, Jiří Sgall

Publication date: 10 October 2017

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.07905

zbMATH Keywords

NP-hardnessgeneral cachingsmall pagesunsplittable flow on a~pathunsplittable flow on a path

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Information storage and retrieval of data (68P20) Flows in graphs (05C21)

Related Items (1)

General caching is hard: even with small pages

Uses Software

• OnlineMin

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A better lower bound on the competitive ratio of the randomized 2-server problem
• Resource allocation with time intervals
• Caching is hard -- even in the fault model
• A strongly competitive randomized paging algorithm
• Competitive analysis of randomized paging algorithms
• On-line file caching
• Page replacement with multi-size pages and applications to web caching
• \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm
• General caching is hard: even with small pages
• Randomized Competitive Algorithms for Generalized Caching
• A quasi-PTAS for unsplittable flow on line graphs
• New Ressults on Server Problems
• Competitive paging algorithms
• New Approximation Schemes for Unsplittable Flow on a Path
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
• A unified approach to approximating resource allocation and scheduling

This page was built for publication: General caching is hard: even with small pages