On complexity of some problems of cluster analysis of vector sequences

DOI10.1134/S1990478913030095zbMath1324.68047OpenAlexW2019101440MaRDI QIDQ5263810

Artem V. Pyatkin, Alexander Kel'Manov

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)

Related Items (10)

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 ⋮ On the complexity of some Euclidean optimal summing problems ⋮ Approximation algorithm for the problem of partitioning a sequence into clusters ⋮ A randomized algorithm for a sequence 2-clustering problem ⋮ An approximation polynomial-time algorithm for a sequence bi-clustering problem ⋮ An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities ⋮ On the complexity and approximability of some Euclidean optimal summing problems ⋮ Complexity of the weighted max-cut in Euclidean space ⋮ A randomized algorithm for two-cluster partition of a set of vectors

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