An approximation polynomial-time algorithm for a sequence bi-clustering problem

DOI10.1134/S0965542515060068zbMath1337.68293OpenAlexW751583333MaRDI QIDQ498594

Alexander Kel'Manov, Sergey Khamidullin

Publication date: 29 September 2015

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

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

zbMATH Keywords

clusteringNP-hardnessapproximation polynomial-time algorithmminimum of the sum of squared distancessequence of Euclidean vectors

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (3)

A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem ⋮ Approximation algorithm for the problem of partitioning a sequence into clusters ⋮ A randomized algorithm for a sequence 2-clustering problem

Uses Software

• ElemStatLearn

Cites Work

• Unnamed Item
• On the complexity of a search for a subset of ``similar vectors
• Off-line detection of a quasi-periodically recurring fragment in a numerical sequence
• NP-hardness of Euclidean sum-of-squares clustering
• Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• On complexity of some problems of cluster analysis of vector sequences
• A 2-approximation polynomial algorithm for a clustering problem
• A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train
• The elements of statistical learning. Data mining, inference, and prediction

This page was built for publication: An approximation polynomial-time algorithm for a sequence bi-clustering problem