An approximating polynomial algorithm for a sequence partitioning problem

DOI10.1134/S1990478914020100MaRDI QIDQ5264726zbMATH OpenOpenAlexFDO

Authors A. V. Kel'manov, S. A. 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)

Recommendations

• An approximation polynomial-time algorithm for a sequence bi-clustering problem
• Approximation algorithm for the problem of partitioning a sequence into clusters
• Exact pseudopolynomial algorithm for one sequence partitioning problem
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities

Cited in

(15)

• Multilevel polynomial partitions and simplified range searching
• scientific article; zbMATH DE number 3987032 (Why is no real title available?)
• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities
• A 2-approximation polynomial algorithm for a clustering problem
• scientific article; zbMATH DE number 4083632 (Why is no real title available?)
• An approximation algorithm for a problem of cluster analysis
• Exact pseudopolynomial algorithm for one sequence partitioning problem
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence
• Approximation algorithm for the problem of partitioning a sequence into clusters
• An approximation polynomial-time algorithm for a sequence bi-clustering problem
• An approximation algorithm for a problem of partitioning a sequence into clusters with restrictions on their cardinalities
• A randomized algorithm for a sequence 2-clustering problem
• An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5264726)