Complexity of certain problems of searching for subsets of vectors and cluster analysis

DOI10.1134/S0965542509110128zbMath1224.68120OpenAlexW1981843437MaRDI QIDQ2995693

Alexander Kel'Manov, Artem V. Pyatkin

Publication date: 4 May 2011

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

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

zbMATH Keywords

complexitypattern recognitionNP-completenesscluster analysisdiscrete extremal problemsearch for subsets

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10)

Related Items (15)

Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem ⋮ On the complexity of some quadratic Euclidean 2-clustering problems ⋮ 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 ⋮ Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters ⋮ NP-hardness of some Euclidean problems of partitioning a finite set of points ⋮ A randomized algorithm for a sequence 2-clustering problem ⋮ Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster ⋮ NP-hardness of some quadratic Euclidean 2-clustering problems ⋮ An approximation polynomial-time algorithm for a sequence bi-clustering problem ⋮ On the complexity of some Euclidean problems of partitioning a finite set of points ⋮ On polynomial solvability of one quadratic Euclidean clustering problem on a line ⋮ Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem ⋮ A randomized algorithm for two-cluster partition of a set of vectors ⋮ K-means clustering via a nonconvex optimization approach

This page was built for publication: Complexity of certain problems of searching for subsets of vectors and cluster analysis