Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
DOI10.15372/SJNM20190201zbMath1497.68450OpenAlexW4231150328MaRDI QIDQ5043014
A. V. Panasenko, Vladimir Khandeev, Alexander Kel'Manov
Publication date: 26 October 2022
Published in: Сибирский журнал вычислительной математики (Search for Journal in Brave)
Full work available at URL: http://mathnet.ru/eng/sjvm705
Euclidean spaceNP-hardnessexact algorithmlargest subset2-clusteringpseudopolynomial-time solvability
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Applications of mathematical programming (90C90) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects of data analysis and big data (68T09)
Related Items (1)
Cites Work
- The planar \(k\)-means problem is NP-hard
- NP-hardness of the Euclidean Max-Cut problem
- On the complexity of a search for a subset of ``similar vectors
- Clustering large graphs via the singular value decomposition
- NP-hardness of some quadratic Euclidean 2-clustering problems
- 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 approximation scheme for metric MAX-CUT
- Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
- A randomized algorithm for two-cluster partition of a set of vectors
- Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
- Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
- On the complexity of some quadratic Euclidean 2-clustering problems
- Exact pseudopolynomial algorithms for a balanced 2-clustering problem
- Solving some vector subset problems by Voronoi diagrams
- A Fully Polynomial-Time Approximation Scheme for a Special Case of a Balanced 2-Clustering Problem
- An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
- P-Complete Approximation Problems
- An Introduction to Statistical Learning
- Data Mining
- A 2-approximation polynomial algorithm for a clustering problem
- Complexity of the weighted max-cut in Euclidean space
- Cluster Analysis and Mathematical Programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems