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

(19)

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

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)