An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities

DOI10.1134/S0081543817090115zbMath1390.68763OpenAlexW2794217424MaRDI QIDQ1744981

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

Publication date: 20 April 2018

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

partitioningapproximation algorithmEuclidean spaceNP-hardnesssequenceminimum 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

• Unnamed Item
• Clustering of time series data -- a survey
• 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
• Data Mining
• On complexity of some problems of cluster analysis of vector sequences
• An approximating polynomial algorithm for a sequence partitioning problem
• An FPTAS for a vector subset search problem