Partitioning a finite set by a dynamic programming method

Publication date 13 October 2004

Published in Automation and Remote Control (Search for Journal in Brave)

discrete optimization dynamic programming optimal partitioning

Dynamic programming in optimal control and differential games (49L20) Dynamic programming (90C39) Minimax problems in mathematical programming (90C47)

Review text

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.

Recommendations

Cited in

(9)

This page was built for publication: Partitioning a finite set by a dynamic programming method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1883748)