On the complexity of some cluster analysis problems

DOI10.1134/S0965542511110108zbMath1249.90190OpenAlexW2050750487MaRDI QIDQ2901122

Alexander Kel'Manov

Publication date: 16 July 2012

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

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

zbMATH Keywords

complexityNP-completenessdiscrete optimizationclusterizationEuclid space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quadratic programming (90C20)

Related Items (7)

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 quadratic Euclidean 2-clustering problems ⋮ A randomized algorithm for two-cluster partition of a set of vectors

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