A 2-approximation polynomial algorithm for a clustering problem

DOI10.1134/S1990478913040066MaRDI QIDQ5263825zbMATH OpenOpenAlexFDO

Authors A. V. Kel'manov, Vladimir Khandeev

Publication date 17 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/s1990478913040066

zbMATH Keywords

cluster analysiscomputational complexityapproximation algorithmapproximation polynomialsearch for a vector subset

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 algorithm for a problem of cluster analysis
• An approximating polynomial algorithm for a sequence partitioning problem
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• An approximation polynomial-time algorithm for a sequence bi-clustering problem
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors

Cited in

(24)

• Easy NP-hardness Proofs of Some Subset Choice Problems
• A randomized algorithm for two-cluster partition of a set of vectors
• An approximation algorithm for solving the problem of the search of a subset of vectors
• Function approximation with polynomial membership functions and alternating cluster estimation
• scientific article; zbMATH DE number 6297742 (Why is no real title available?)
• Randomized Algorithm of Finding the True Number of Clusters Based on Chebychev Polynomial Approximation
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• Exact algorithms for size constrained 2-clustering in the plane
• An asymptotically exact polynomial algorithm for equipartition problems
• PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem
• An approximation algorithm for a problem of cluster analysis
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• An approximation scheme for a problem of search for a vector subset
• A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• A 2-approximation algorithm for the graph 2-clustering problem
• PTAS for problems of vector choice and clustering with different centers
• Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
• An approximation polynomial-time algorithm for a sequence bi-clustering problem
• scientific article; zbMATH DE number 1629976 (Why is no real title available?)
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems

This page was built for publication: A 2-approximation polynomial algorithm for a clustering problem

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