An approximating polynomial algorithm for a sequence partitioning problem

DOI10.1134/S1990478914020100zbMath1324.68243OpenAlexW2109886072MaRDI QIDQ5264726

Alexander Kel'Manov, Sergey Khamidullin

Publication date: 27 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/s1990478914020100

zbMATH Keywords

clusteringNP-hardnessminimum sum-of-squared distancesEuclidean vector sequencepolynomial 2-approximation algorithm

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem ⋮ A randomized algorithm for a sequence 2-clustering problem ⋮ 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence ⋮ An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities

This page was built for publication: An approximating polynomial algorithm for a sequence partitioning problem