On the complexity of some cluster analysis problems

DOI10.1134/S0965542511110108MaRDI QIDQ2901122zbMATH OpenOpenAlexFDO

Authors A. V. Kel'manov

Publication date 16 July 2012

Published in Zhurnal Vychislitel'noĭ Matematiki i Matematicheskoĭ Fiziki (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0965542511110108

zbMATH Keywords

complexityNP-completenessdiscrete optimizationclusterizationEuclid space

Mathematics Subject Classification ID

Quadratic programming (90C20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 6007853
• scientific article; zbMATH DE number 4034897
• scientific article; zbMATH DE number 2081029
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• An approximation algorithm for a problem of cluster analysis
• On complexity of some problems of cluster analysis of vector sequences
• On the Complexity of Clustering with Relaxed Size Constraints
• The complexity of the simultaneous cluster problem
• scientific article; zbMATH DE number 7746258
• On the complexity of clustering with relaxed size constraints in fixed dimension

Cited in

(21)

• A randomized algorithm for two-cluster partition of a set of vectors
• scientific article; zbMATH DE number 2011857 (Why is no real title available?)
• On the Complexity of Clustering with Relaxed Size Constraints
• Studying Complexity of Model-based Clustering
• Regarding the complexity of additive clustering models: comment on Lee (2001).
• Some computational issues in cluster analysis with no a priori metric
• scientific article; zbMATH DE number 6007853 (Why is no real title available?)
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• Italian contributions on some recent research topics in cluster analysis
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• Probabilistic analysis of two \(k\)-cluster problems
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• NP-hardness of some quadratic Euclidean 2-clustering problems
• ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM
• scientific article; zbMATH DE number 1927359 (Why is no real title available?)
• scientific article; zbMATH DE number 3930160 (Why is no real title available?)
• SOFSEM 2006: Theory and Practice of Computer Science
• On the complexity of some quadratic Euclidean 2-clustering problems
• Estimating the clustering coefficient using sample complexity analysis
• scientific article; zbMATH DE number 3984569 (Why is no real title available?)

This page was built for publication: On the complexity of some cluster analysis problems

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