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

DOI10.1007/978-3-319-44914-2_14MaRDI QIDQ3133210zbMATH OpenOpenAlexFDO

Authors L. V. Mikhailova, A. V. Kel'manov, S. A. Khamidullin, Vladimir Khandeev

Publication date 13 February 2018

Published in Discrete Optimization and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-44914-2_14

zbMATH Keywords

clusteringNP-hardnessEuclidean spacestructural constraintsminimum sum-of-squared distancesguaranteed approximation factor

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(6)

• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities
• A sequential aggregation algorithm for the set partitioning problem
• An exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Approximation algorithm for the problem of partitioning a sequence into clusters
• An approximation polynomial-time algorithm for a sequence bi-clustering problem

This page was built for publication: An approximation algorithm for a problem of partitioning a sequence into clusters with restrictions on their cardinalities

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