Approximation algorithm for the problem of partitioning a sequence into clusters

DOI10.1134/S0965542517080085zbMath1423.68596OpenAlexW2751508009MaRDI QIDQ1683189

L. V. Mikhailova, Alexander Kel'Manov, Sergey Khamidullin, Vladimir Khandeev

Publication date: 6 December 2017

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

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

zbMATH Keywords

partitionapproximation algorithmEuclidean spaceNP-hardnesssequenceminimum of the sum of squared distances

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• An approximation polynomial-time algorithm for a sequence bi-clustering problem
• Clustering of time series data -- a survey
• A posteriori joint detection of reference fragments in a quasi-periodic sequence
• Data Mining
• On complexity of some problems of cluster analysis of vector sequences
• An FPTAS for a vector subset search problem