Document Open Access Logo

Dynamic Maintenance of Monotone Dynamic Programs and Applications

Authors Monika Henzinger , Stefan Neumann , Harald Räcke , Stefan Schmid

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.36.pdf
  • Filesize: 0.83 MB
  • 16 pages

Document Identifiers

Author Details

Monika Henzinger
  • Institute of Science and Technology Austria, Klosterneuburg, Austria
Stefan Neumann
  • KTH Royal Institute of Technology, Stockholm, Sweden
Harald Räcke
  • TU München, Germany
Stefan Schmid
  • TU Berlin, Germany
  • Fraunhofer SIT, Darmstadt, Germany

Funding

  • Henzinger, Monika: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 "The Design of Modern Fully Dynamic Data Structures (MoDynStruct)" and from the Austrian Science Fund (FWF) project "Fast Algorithms for a Reactive Network Layer (ReactNet)", P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020-2024.
  • Neumann, Stefan: This research is supported by the the ERC Advanced Grant REBOUND (834862) and the EC H2020 RIA project SoBigData++ (871042).
  • Schmid, Stefan: Research supported by Austrian Science Fund (FWF) project I 5025-N (DELTA), 2020-2024.

Cite AsGet BibTex

Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid. Dynamic Maintenance of Monotone Dynamic Programs and Applications. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.36

Abstract

Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing (1+ε)-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-n DP table rows with entries in [0,W] using only polylog(n,W) bits, and to perform operations, such as (min,+)-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of k-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic programming
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Packing and covering problems
Keywords
  • Dynamic programming
  • dynamic algorithms
  • data structures

Metrics

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

Related Versions

References

  1. Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195-208, 1987. Google Scholar
  2. Konstantin Andreev, Charles Garrod, Daniel Golovin, Bruce M. Maggs, and Adam Meyerson. Simultaneous source location. ACM Trans. Algorithms, 6(1):16:1-16:17, 2009. Google Scholar
  3. Konstantin Andreev and Harald Räcke. Balanced graph partitioning. Theory of Computing Systems, 39(6):929-939, 2006. Google Scholar
  4. Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, and Yan Zhang. The knuth-yao quadrangle-inequality speedup is a consequence of total monotonicity. ACM Trans. Algorithms, 6(1):17:1-17:22, 2009. Google Scholar
  5. Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. In Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 117-158. Springer, 2016. Google Scholar
  6. Rainer E. Burkard, Bettina Klinz, and Rüdiger Rudolf. Perspectives of monge properties in optimization. Discret. Appl. Math., 70(2):95-161, 1996. Google Scholar
  7. Timothy M. Chan. Approximation schemes for 0-1 knapsack. In SOSA, volume 61, pages 5:1-5:12, 2018. Google Scholar
  8. Timothy M. Chan. Near-optimal randomized algorithms for selection in totally monotone matrices. In SODA, pages 1483-1495, 2021. Google Scholar
  9. Spencer Compton, Slobodan Mitrovic, and Ronitt Rubinfeld. New partitioning techniques and faster algorithms for approximate interval scheduling. CoRR, abs/2012.15002, 2020. URL: http://arxiv.org/abs/2012.15002.
  10. Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In ICLR, 2020. Google Scholar
  11. Franziska Eberle, Nicole Megow, Lukas Nölke, Bertrand Simon, and Andreas Wiese. Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time. In FSTTCS, volume 213, pages 18:1-18:17, 2021. Google Scholar
  12. David Eppstein, Zvi Galil, and Raffaele Giancarlo. Speeding up dynamic programming. In FOCS, pages 488-496. IEEE Computer Society, 1988. Google Scholar
  13. Guy Even, Joseph Naor, Satish Rao, and Baruch Schieber. Fast approximate graph partitioning algorithms. SIAM J. Comput., 28(6):2187-2214, 1999. Google Scholar
  14. Uriel Feige and Robert Krauthgamer. A polylogarithmic approximation of the minimum bisection. SIAM J. Comput., 31(4):1090-1118, 2002. Google Scholar
  15. Andreas Emil Feldmann and Luca Foschini. Balanced partitions of trees and applications. Algorithmica, 71(2):354-376, 2015. Google Scholar
  16. Zvi Galil and Kunsoo Park. Dynamic programming with convexity, concavity, and sparsity. Theor. Comput. Sci., 92(1):49-76, 1992. Google Scholar
  17. Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid. Dynamic maintenance of monotone dynamic programs and applications. CoRR, abs/2301.01744, 2024. Full version of this paper. URL: http://arxiv.org/abs/2301.01744.
  18. Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In SoCG, volume 164 of LIPIcs, pages 51:1-51:14, 2020. Google Scholar
  19. George Karypis and Vipin Kumar. Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, 1997. Google Scholar
  20. Donald E. Knuth. Optimum binary search trees. Acta Informatica, 1:14-25, 1971. Google Scholar
  21. Gary L. Miller, Richard Peng, Russell Schwartz, and Charalampos E. Tsourakakis. Approximate dynamic programming using halfspace queries and multiscale monge decomposition. In SODA, pages 1675-1682, 2011. Google Scholar
  22. Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. Mem. Math. Phys. Acad. Royale Sci., pages 666-704, 1781. Google Scholar
  23. Peter Sanders and Christian Schulz. Think locally, act globally: Highly balanced graph partitioning. In SEA, volume 7933, pages 164-175, 2013. Google Scholar
  24. F. Frances Yao. Efficient dynamic programming using quadrangle inequalities. In STOC, pages 429-435, 1980. 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