On complexity of some problems of cluster analysis of vector sequences

DOI10.1134/S1990478913030095MaRDI QIDQ5263810zbMATH OpenOpenAlexFDO

Authors A. V. Kel'manov, Artem Pyatkin

Publication date 17 July 2015

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

clusteringalgorithmic complexityEuclidean vector sequenceminimum sum of the squares of distancesrestriction on vector indices

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the complexity of some Euclidean problems of partitioning a finite set of points
• NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters
• NP-hardness of some Euclidean problems of partitioning a finite set of points
• Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors

Cited in

(20)

• A randomized algorithm for two-cluster partition of a set of vectors
• On the complexity of some cluster analysis problems
• On the complexity of some data analysis problems
• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities
• scientific article; zbMATH DE number 3921982 (Why is no real title available?)
• Extremes in the Complexity of Computing Metric Distances Between Partitions
• scientific article; zbMATH DE number 2081029 (Why is no real title available?)
• Norm statistics and the complexity of clustering problems
• On metric clustering
• Complexity of the weighted max-cut in Euclidean space
• 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
• On the complexity of some Euclidean optimal summing problems
• Momentopes, the complexity of vector partitioning, and Davenport-Schinzel sequences
• Approximation algorithm for the problem of partitioning a sequence into clusters
• An approximation polynomial-time algorithm for a sequence bi-clustering problem
• On the complexity and approximability of some Euclidean optimal summing problems
• A randomized algorithm for a sequence 2-clustering problem
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• Sequence spaces \(M(\phi)\) and \(N(\phi)\) with application in clustering

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

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