Optimising sum-of-squares measures for clustering multisets defined over a metric space

DOI10.1016/J.DAM.2013.04.015MaRDI QIDQ2444542zbMATH OpenOpenAlexFDO

Authors George Kettleborough, V. J. Rayward-Smith

Publication date 10 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.04.015

zbMATH Keywords

clusteringcomplexityNP-completenessoptimisationsum-of-squares

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Learning and adaptive systems in artificial intelligence (68T05) Pattern recognition, speech recognition (68T10)

Recommendations

• On the complexity of some quadratic Euclidean 2-clustering problems
• NP-hardness of some quadratic Euclidean 2-clustering problems
• Approximating min-sum k -clustering in metric spaces
• On metric clustering
• NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes

Cites work

• \(k\)-means requires exponentially many iterations even in the plane
• A Branch-and-Bound Approach Using Polyhedral Results for a Clustering Problem
• A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning
• A repetitive branch-and-bound procedure for minimum within-cluster sums of squares partitioning
• An Interior Point Algorithm for Minimum Sum-of-Squares Clustering
• Cluster analysis and mathematical programming
• Clustering rules: A comparison of partitioning and hierarchical clustering algorithms
• Comparing clusterings -- an information based distance
• scientific article; zbMATH DE number 3678973 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1149439 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• scientific article; zbMATH DE number 4189544 (Why is no real title available?)
• NP-hardness of Euclidean sum-of-squares clustering
• Smoothed analysis of the k-means method
• The Planar k-Means Problem is NP-Hard

Cited in

(3)

• A hybrid algorithm with cluster analysis in modelling high dimensional data
• Fixed set search applied to the clique partitioning problem
• On estimation and order selection for multivariate extremes via clustering

This page was built for publication: Optimising sum-of-squares measures for clustering multisets defined over a metric space

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