---
_id: '12760'
abstract:
- lang: eng
  text: "Dynamic programming (DP) is one of the fundamental paradigms in algorithm
    design. However,\r\nmany 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.\r\nIn 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\r\na novel data structure for computing (1
    + ϵ)-approximate DP solutions in near-linear time and\r\nspace in the static setting,
    and with polylogarithmic update times when the DP entries change\r\ndynamically.
    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.\r\nWe 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."
acknowledgement: "Monika Henzinger: This project has received funding from the European
  Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
  programme (Grant\r\nagreement 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.\r\nStefan Neumann: This research
  is supported by the the ERC Advanced Grant REBOUND (834862) and the EC H2020 RIA
  project SoBigData++ (871042).\r\nStefan Schmid: Research supported by Austrian Science
  Fund (FWF) project I 5025-N (DELTA), 2020-2024."
alternative_title:
- LIPIcs
article_number: '36'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Stefan
  full_name: Neumann, Stefan
  last_name: Neumann
- first_name: Harald
  full_name: Räcke, Harald
  last_name: Räcke
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'Henzinger MH, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone
    dynamic programs and applications. In: <i>40th International Symposium on Theoretical
    Aspects of Computer Science</i>. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik; 2023. doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2023.36">10.4230/LIPIcs.STACS.2023.36</a>'
  apa: 'Henzinger, M. H., Neumann, S., Räcke, H., &#38; Schmid, S. (2023). Dynamic
    maintenance of monotone dynamic programs and applications. In <i>40th International
    Symposium on Theoretical Aspects of Computer Science</i> (Vol. 254). Hamburg,
    Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.STACS.2023.36">https://doi.org/10.4230/LIPIcs.STACS.2023.36</a>'
  chicago: Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic
    Maintenance of Monotone Dynamic Programs and Applications.” In <i>40th International
    Symposium on Theoretical Aspects of Computer Science</i>, Vol. 254. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2023. <a href="https://doi.org/10.4230/LIPIcs.STACS.2023.36">https://doi.org/10.4230/LIPIcs.STACS.2023.36</a>.
  ieee: M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance
    of monotone dynamic programs and applications,” in <i>40th International Symposium
    on Theoretical Aspects of Computer Science</i>, Hamburg, Germany, 2023, vol. 254.
  ista: 'Henzinger MH, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of
    monotone dynamic programs and applications. 40th International Symposium on Theoretical
    Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer
    Science, LIPIcs, vol. 254, 36.'
  mla: Henzinger, Monika H., et al. “Dynamic Maintenance of Monotone Dynamic Programs
    and Applications.” <i>40th International Symposium on Theoretical Aspects of Computer
    Science</i>, vol. 254, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2023, doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2023.36">10.4230/LIPIcs.STACS.2023.36</a>.
  short: M.H. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 40th International
    Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2023.
conference:
  end_date: 2023-03-09
  location: Hamburg, Germany
  name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
  start_date: 2023-03-07
date_created: 2023-03-26T22:01:07Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-03-27T06:46:27Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.STACS.2023.36
external_id:
  arxiv:
  - '2301.01744'
file:
- access_level: open_access
  checksum: 22141ab8bc55188e2dfff665e5daecbd
  content_type: application/pdf
  creator: dernst
  date_created: 2023-03-27T06:37:22Z
  date_updated: 2023-03-27T06:37:22Z
  file_id: '12769'
  file_name: 2023_LIPICS_HenzingerM.pdf
  file_size: 872706
  relation: main_file
  success: 1
file_date_updated: 2023-03-27T06:37:22Z
has_accepted_license: '1'
intvolume: '       254'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
publication: 40th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
  isbn:
  - '9783959772662'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic maintenance of monotone dynamic programs and applications
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 254
year: '2023'
...