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+\varepsilon)$-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.
翻译:动态编程 (DP) 是算法设计的基本范式之一 。 然而, 许多 DP 算法必须填入大型 DP 表格, 以二维阵列为代表, 这至少导致四级运行时间和空间使用。 这导致当 DP 满足额外属性时, 比如, 蒙古属性或完全单调性 等, 开发出更完善的特例算法 。 在本文中, 我们考虑一个新的条件, 假设( 在其它技术假设中) DP 表格的行是单数 。 在此假设下, 我们引入一个新的数据结构, 用于在近线时间和空间计算 $ (1 ⁇ varepsil) $ ($- pal- appoint DP), 并在 DP 输入时, 仅将 美元 美元 的 美元 的 DP 值 自动更新 。 根据我们的知识, 我们的新条件无法根据现有 DP 的 获取动态 。 我们只能用二维数 的阵列的阵列数行, 将 DP 的 值 值 的 值 以 美元 美元 美元 。