Partitioning a finite set by a dynamic programming method
type: Item
instance of: scholarly article
title: Partitioning a finite set by a dynamic programming method
zbMATH Open document ID: 1062.93021
author: A. G. Chentsov
author: P. A. Chentsov
published in: Automation and Remote Control
publication date: 2004-10-13T00:00:00Z
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.
Mathematics Subject Classification ID: 93B40
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90C47
Mathematics Subject Classification ID: 49L20
zbMATH DE Number: 2107738
zbMATH Keywords: optimal partitioning
zbMATH Keywords: dynamic programming
zbMATH Keywords: discrete optimization
reviewed by: D. B. Silin
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2107738