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)

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

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)