Document Open Access Logo

Breaking the Barrier of 2 for the Storage Allocation Problem

Authors Tobias Mömke , Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.86.pdf
  • Filesize: 0.58 MB
  • 19 pages

Document Identifiers

Author Details

Tobias Mömke
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Andreas Wiese
  • Department of Industrial Engineering, Universidad de Chile, Santiago, Chile

Funding

  • Mömke, Tobias: This work was partially supported by the ERC Advanced Investigators Grant 695614 (https://powver.org), and by DFG Grant 389792660 as part of TRR 248 (https://perspicuous-computing.science).
  • Wiese, Andreas: Partially supported by FONDECYT Regular grant 1170223.

Cite AsGet BibTex

Tobias Mömke and Andreas Wiese. Breaking the Barrier of 2 for the Storage Allocation Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 86:1-86:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.86

Abstract

Packing problems are an important class of optimization problems. The probably most well-known problem if this type is knapsack and many generalizations of it have been studied in the literature like Two-dimensional Geometric Knapsack (2DKP) and Unsplittable Flow on a Path (UFP). For the latter two problems, recently the first polynomial time approximation algorithms with better approximation ratios than 2 were presented [Gálvez et al., FOCS 2017][Grandoni et al., STOC 2018]. In this paper we break the barrier of 2 for the Storage Allocation Problem (SAP), a problem which combines properties of 2DKP and UFP. In SAP, we are given a path with capacitated edges and a set of tasks where each task has a start vertex, an end vertex, a size, and a profit. We seek to select the most profitable set of tasks that we can draw as non-overlapping rectangles underneath the capacity profile of the edges where the height of each rectangle equals the size of the corresponding task. The problem SAP appears naturally in settings of allocating resources like memory, bandwidth, etc. where each request needs a contiguous portion of the resource. The best known polynomial time approximation algorithm for SAP has an approximation ratio of 2+ε [Mömke and Wiese, ICALP 2015] and no better quasi-polynomial time algorithm is known. We present a polynomial time (63/32+ε) < 1.969-approximation algorithm for the important case of uniform edge capacities and a quasi-polynomial time (1.997+ε)-approximation algorithm for non-uniform quasi-polynomially bounded edge capacities. Key to our results are building blocks consisting of stair-blocks, jammed tasks, and boxes that we use to construct profitable solutions and which allow us to compute solutions of these types efficiently. Finally, using our techniques we show that under slight resource augmentation we can obtain even approximation ratios of 3/2+ε in polynomial time and 1+ε in quasi-polynomial time, both for arbitrary edge capacities.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic programming
  • Theory of computation → Packing and covering problems
  • Theory of computation → Rounding techniques
Keywords
  • Approximation Algorithms
  • Resource Allocation
  • Dynamic Programming

Metrics

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

Related Versions

References

  1. Anna Adamaszek and Andreas Wiese. A quasi-PTAS for the two-dimensional geometric knapsack problem. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1491-1505. SIAM, 2015. Google Scholar
  2. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing 2+ε approximation for unsplittable flow on a path. In SODA, 2014. Google Scholar
  3. N. Bansal, A. Chakrabarti, A. Epstein, and B. Schieber. A quasi-PTAS for unsplittable flow on line graphs. In STOC, pages 721-729. ACM, 2006. Google Scholar
  4. N. Bansal, Z. Friggstad, R. Khandekar, and R. Salavatipour. A logarithmic approximation for unsplittable flow on line graphs. In SODA, pages 702-709, 2009. Google Scholar
  5. Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, and Maxim Sviridenko. A structural lemma in 2-dimensional packing, and its implications on approximability. In Algorithms and Computation, pages 77-86. Springer, 2009. Google Scholar
  6. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. Journal of the ACM (JACM), 48(5):1069-1090, 2001. Google Scholar
  7. Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz. Resource allocation in bounded degree trees. Algorithmica, 54(1):89-106, 2009. Google Scholar
  8. Reuven Bar-Yehuda, Michael Beder, and Dror Rawitz. A constant factor approximation algorithm for the storage allocation problem. Algorithmica, 77(4):1105-1127, 2017. Google Scholar
  9. Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese. New approximation schemes for unsplittable flow on a path. In SODA, pages 47-58, 2015. URL: https://doi.org/10.1137/1.9781611973730.5.
  10. Paul Bonsma, Jens Schulz, and Andreas Wiese. A constant-factor approximation algorithm for unsplittable flow on paths. SIAM Journal on Computing, 43:767-799, 2014. Google Scholar
  11. Adam L Buchsbaum, Howard Karloff, Claire Kenyon, Nick Reingold, and Mikkel Thorup. Opt versus load in dynamic storage allocation. SIAM Journal on Computing, 33(3):632-646, 2004. Google Scholar
  12. Gruia Călinescu, Amit Chakrabarti, Howard J. Karloff, and Yuval Rabani. An improved approximation algorithm for resource allocation. ACM Transactions on Algorithms, 7:48:1-48:7, 2011. URL: https://doi.org/10.1145/2000807.2000816.
  13. A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar. Approximation algorithms for the unsplittable flow problem. Algorithmica, 47:53-78, 2007. Google Scholar
  14. C. Chekuri, A. Ene, and N. Korula. Unsplittable flow in paths and trees and column-restricted packing integer programs. In APPROX-RANDOM, pages 42-55, 2009. Google Scholar
  15. C. Chekuri, M. Mydlarz, and F. Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms, 3, 2007. Google Scholar
  16. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via l-packings. In 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 260-271. IEEE, 2017. Google Scholar
  17. Jordan Gergov. Approximation algorithms for dynamic storage allocation. In Algorithms-ESA'96, pages 52-61. Springer, 1996. Google Scholar
  18. Jordan Gergov. Algorithms for compile-time memory optimization. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pages 907-908. Society for Industrial and Applied Mathematics, 1999. Google Scholar
  19. 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 SODA, pages 2411-2422, 2017. Google Scholar
  20. 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 SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 607-619, 2018. URL: https://doi.org/10.1145/3188745.3188894.
  21. Sandy Heydrich and Andreas Wiese. Faster approximation schemes for the two-dimensional knapsack problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 79-98, 2017. URL: https://doi.org/10.1137/1.9781611974782.6.
  22. Klaus Jansen and Roberto Solis-Oba. A polynomial time approximation scheme for the square packing problem. In Andrea Lodi, Alessandro Panconesi, and Giovanni Rinaldi, editors, Integer Programming and Combinatorial Optimization, pages 184-198, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  23. Klaus Jansen and Guochuan Zhang. Maximizing the number of packed rectangles. In Scandinavian Workshop on Algorithm Theory, pages 362-371. Springer, 2004. Google Scholar
  24. Klaus Jansen and Guochuan Zhang. Maximizing the total profit of rectangles packed into a rectangle. Algorithmica, 47(3):323-342, 2007. Google Scholar
  25. Hal A Kierstead. The linearity of first-fit coloring of interval graphs. SIAM Journal on Discrete Mathematics, 1(4):526-530, 1988. Google Scholar
  26. Hal A Kierstead. A polynomial time approximation algorithm for dynamic storage allocation. Discrete Mathematics, 88(2):231-237, 1991. Google Scholar
  27. Tobias Mömke and Andreas Wiese. A (2+ε)-approximation algorithm for the storage allocation problem. In Proceedings of the 42superscriptnd Annual International Colloquium on Automata, Languages and Programming (ICALP 2015), volume 9134 of Lecture Notes in Computer Science, pages 973-984. Springer, 2015. Google Scholar
  28. Tobias Mömke and Andreas Wiese. Breaking the barrier of 2 for the storage allocation problem. CoRR, abs/1911.10871, 2019. URL: http://arxiv.org/abs/1911.10871.
  29. C. A. Phillips, R. N. Uma, and J. Wein. Off-line admission control for general scheduling problems. In Proceedings of the 11superscriptth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), pages 879-888. ACM, 2000. 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