Partitioning a finite set by a dynamic programming method (Q1883748): Difference between revisions

The following discrete optimal partitioning problem is studied. Given an integer \(N\), \(N\geq2\), \(\text{\textbf{K}}\) is a subset of integers between \(1\) and \(N\). The set of all disjoint partitions into \(m\) subsets \(K_i\), \(\text{\textbf{K}}=\bigcup_{i=1}^mK_i\) is denoted by \(\Delta_m(\text{\textbf{K}})\). Real-valued functionals \(T_i\) are defined on subsets of \(\left\{1,2,\ldots,N\right\}\). The problem is to find a partition from \(\Delta_m(\text{\textbf{K}})\) at which the minimum \[ \theta_m(\text{\textbf{K}})= \min_{\Delta_m(\text{\textbf{K}})}\sup\left\{ T_i(K_i) \right\} \] is attained. The minimizing partition is constructed using the method of dynamic programming. The latter is applied based on the recursive formula \[ \theta_{m+1}(L)=\min_\Lambda\sup\left\{ \theta_m(L\backslash\Lambda),\, T_{m+1}(\Lambda) \right\}. \] An example of application of the proposed procedure is presented. The dynamic programming is parameterized in the case where the sets \(K_i\) are contingent integer intervals. The reviewed work is not an easy reading. Unfortunately, in addition, it includes references to items that are missing in the bibliography.