An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors

DOI10.1134/S1990478915040067zbMath1349.68151OpenAlexW2275454988MaRDI QIDQ3186839

Alexander Kel'Manov, Vladimir Khandeev

Publication date: 12 August 2016

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

partitioningNP-hardnesssquared Euclidean distanceexact pseudopolynomial algorithmvector subset

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems, Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters, 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, An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities, Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A randomized algorithm for two-cluster partition of a set of vectors
• Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов
• 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