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

DOI10.1134/S0965542515060068MaRDI QIDQ498594zbMATH OpenOpenAlexFDO

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

Recommendations

• An approximating polynomial algorithm for a sequence partitioning problem
• Approximation algorithm for the problem of partitioning a sequence into clusters
• 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 restrictions on their cardinalities
• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities

Cites work

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

Cited in

(11)

• 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
• The biclique \(k\)-clustering problem in bipartite graphs and its application in bioinformatics
• Exact pseudopolynomial algorithm for one sequence partitioning problem
• Computing and Combinatorics
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• Sequential clustering with radius and split criteria
• Approximation algorithm for the problem of partitioning a sequence into clusters
• 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 approximating polynomial algorithm for a sequence partitioning problem

Describes a project that uses

Uses Software

• ElemStatLearn

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

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