Document Open Access Logo

Better Approximations for General Caching and UFP-Cover Under Resource Augmentation

Authors Andrés Cristi , Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.44.pdf
  • Filesize: 480 kB
  • 14 pages

Document Identifiers

Author Details

Andrés Cristi
  • Universidad de Chile, Chile
Andreas Wiese
  • Universidad de Chile, Chile

Funding

  • Cristi, Andrés: Supported by CONICYT-PFCHA/Doctorado Nacional/2018-21180347.
  • Wiese, Andreas: Partially supported by FONDECYT Regular grant 1170223.

Cite AsGet BibTex

Andrés Cristi and Andreas Wiese. Better Approximations for General Caching and UFP-Cover Under Resource Augmentation. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.44

Abstract

In the Unsplittable Flow on a Path Cover (UFP-cover) problem we are given a path with a demand for each edge and a set of tasks where each task is defined by a subpath, a size and a cost. The goal is to select a subset of the tasks of minimum cost that together cover the demand of each edge. This problem models various resource allocation settings and also the general caching problem. The best known polynomial time approximation ratio for it is 4 [Bar-Noy et al., STOC 2000]. In this paper, we study the resource augmentation setting in which we need to cover only a slightly smaller demand on each edge than the compared optimal solution. If the cost of each task equals its size (which represents the natural bit-model in the related general caching problem) we provide a polynomial time algorithm that computes a solution of optimal cost. We extend this result to general caching and to the packing version of Unsplittable Flow on a Path in their respective natural resource augmentation settings. For the case that the cost of each task equals its "area", i.e., the product of its size and its path length, we present a polynomial time (1+ε)-approximation for UFP-cover. If additionally the edge capacities are in a constant range we compute even a solution of optimal cost and also obtain a PTAS without resource augmentation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • General caching
  • unsplittable flow cover
  • approximation algorithm
  • resource augmentation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Susanne Albers, Sanjeev Arora, and Sanjeev Khanna. Page replacement for general caching problems. In SODA, volume 99, pages 31-40. Citeseer, 1999. Google Scholar
  2. Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, and Andreas Wiese. A QPTAS for the General Scheduling Problem with Identical Release Dates. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.31.
  3. Nikhil Bansal, Amit Chakrabarti, Amir Epstein, and Baruch Schieber. A quasi-PTAS for unsplittable flow on line graphs. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006), pages 721-729. ACM, 2006. Google Scholar
  4. Nikhil Bansal, Ravishankar Krishnaswamy, and Barna Saha. On capacitated set cover problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 38-49. Springer, 2011. Google Scholar
  5. Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. SIAM Journal on Computing, 43(5):1684-1698, 2014. Google Scholar
  6. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. J. ACM, 48(5):1069-1090, September 2001. URL: https://doi.org/10.1145/502102.502107.
  7. Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese. New approximation schemes for unsplittable flow on a path. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 47-58, 2015. URL: https://doi.org/10.1137/1.9781611973730.5.
  8. Laszlo A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems journal, 5(2):78-101, 1966. Google Scholar
  9. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 2005. Google Scholar
  10. Robert D Carr, Lisa K Fleischer, Vitus J Leung, and Cynthia A Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms (SODA 2000), pages 106-115. Society for Industrial and Applied Mathematics, 2000. Google Scholar
  11. Deeparnab Chakrabarty, Elyot Grant, and Jochen Könemann. On column-restricted and priority covering integer programs. In International Conference on Integer Programming and Combinatorial Optimization, pages 355-368. Springer, 2010. Google Scholar
  12. Maurice Cheung, Julián Mestre, David B Shmoys, and José Verschae. A primal-dual approximation algorithm for min-sum single-machine scheduling problems. SIAM Journal on Discrete Mathematics, 31(2):825-838, 2017. Google Scholar
  13. M. Chrobak, G. Woeginger, K. Makino, and H. Xu. Caching is hard, even in the fault model. In ESA, pages 195-206, 2010. Google Scholar
  14. Marek Chrobak, H Karloof, Tom Payne, and S Vishwnathan. New results on server problems. SIAM Journal on Discrete Mathematics, 4(2):172-181, 1991. Google Scholar
  15. Amos Fiat, Richard M Karp, Michael Luby, Lyle A McGeoch, Daniel D Sleator, and Neal E Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991. Google Scholar
  16. P. A. Franaszek and T. J. Wagner. Some distribution-free aspects of paging algorithm performance. J. ACM, 21(1):31-39, January 1974. URL: https://doi.org/10.1145/321796.321800.
  17. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. To augment or not to augment: Solving unsplittable flow on a path by creating slack. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), 2017. To appear. Google Scholar
  18. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. A (5/3+ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pages 607-619. ACM, 2018. Google Scholar
  19. Wiebke Höhn, Julián Mestre, and Andreas Wiese. How unsplittable-flow-covering helps scheduling with job-dependent cost functions. Algorithmica, 80(4):1191-1213, 2018. Google Scholar
  20. Sandy Irani. Page replacement with multi-size pages and applications to web caching. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 701-710. ACM, 1997. Google Scholar
  21. Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact