Dynamic programming and convex clustering

DOI10.1007/BF01182769MaRDI QIDQ1314428zbMATH OpenOpenAlexFDO

Authors Vladimir Batagelj, Simona Korenjak-Černe, Sandi Klavžar

Publication date 16 February 1994

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01182769

zbMATH Keywords

\(k\)-clustering problemslinear ordered setssufficient conditions for convexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 907944
• Improving dynamic programming strategies for partitioning
• Polynomial algorithms for nested univariate clustering
• Combinatorial data analysis. Optimization by dynamic programming

Cites work

• A Dynamic Programming Algorithm for Cluster Analysis
• Cluster Analysis and Mathematical Programming
• Clustering with relational constraint
• scientific article; zbMATH DE number 3942804 (Why is no real title available?)
• scientific article; zbMATH DE number 3579840 (Why is no real title available?)
• scientific article; zbMATH DE number 3996907 (Why is no real title available?)
• On Grouping for Maximum Homogeneity
• Optimal Set Partitioning

Cited in

(9)

• Combinatorial data analysis. Optimization by dynamic programming
• Computing exact clustering posteriors with subset convolution
• Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization
• scientific article; zbMATH DE number 4036950 (Why is no real title available?)
• scientific article; zbMATH DE number 907944 (Why is no real title available?)
• scientific article; zbMATH DE number 7370526 (Why is no real title available?)
• scientific article; zbMATH DE number 3892396 (Why is no real title available?)
• scientific article; zbMATH DE number 4195735 (Why is no real title available?)
• Improving dynamic programming strategies for partitioning

This page was built for publication: Dynamic programming and convex clustering

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