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

algorithmic complexityclusteringEuclidean 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

(21)

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

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)