Dynamic programming and convex clustering (Q1314428)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Dynamic programming and convex clustering |
scientific article |
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
