A randomized algorithm for two-cluster partition of a set of vectors

DOI10.1134/S096554251502013XzbMath1331.68288OpenAlexW2024411200MaRDI QIDQ2354448

Alexander Kel'Manov, Vladimir Khandeev

Publication date: 13 July 2015

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

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

zbMATH Keywords

partitionasymptotic accuracyrandomized algorithmNP-hardnessset of vectorssquared Euclidean distances

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems, Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem, A randomized algorithm for finding a subset of vectors with the maximum Euclidean norm of their sum, An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors, A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem, Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters, A randomized algorithm for a sequence 2-clustering problem, Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster, Exact pseudopolynomial algorithms for a balanced 2-clustering problem, Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center, Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability, Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
• NP-hardness of the Euclidean Max-Cut problem
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• 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
• Cluster analysis and mathematical programming
• Minimum sum of squares clustering in a low dimensional space
• Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов
• On the complexity of some cluster analysis problems
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• On the complexity of some data analysis problems
• On complexity of some problems of cluster analysis of vector sequences
• A 2-approximation polynomial algorithm for a clustering problem
• Cluster Analysis and Mathematical Programming