Dynamic programming and convex clustering (Q1314428)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Dynamic programming and convex clustering |
scientific article; zbMATH DE number 502842
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Dynamic programming and convex clustering |
scientific article; zbMATH DE number 502842 |
Statements
Dynamic programming and convex clustering (English)
0 references
16 February 1994
0 references
A dynamic programming procedure is developed for \(k\)-clustering problems for linear ordered sets. If the problem has an optimal solution which is convex (which implies that the cluster sets are intervals) then the dynamic programming approach gives an \(O(kn^ 3)\)-algorithm where \(n\) is the number of items. Sufficient conditions for convexity are derived.
0 references
sufficient conditions for convexity
0 references
\(k\)-clustering problems
0 references
linear ordered sets
0 references
