On the complexity of some quadratic Euclidean 2-clustering problems

DOI10.1134/S096554251603009XzbMath1362.68092OpenAlexW2440461674MaRDI QIDQ2630045

Alexander Kel'Manov, Artem V. Pyatkin

Publication date: 8 July 2016

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

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

zbMATH Keywords

Euclidean spaceoptimization problemscluster analysisNP-hard problemminimum of the sum of squares of distances between elements of a clusterpartition of a finite set

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ NP-hardness of \(m\)-dimensional weighted matching problems ⋮ 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 ⋮ Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

Uses Software

• PRMLT

Cites Work

• 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
• On the complexity of a search for a subset of ``similar vectors
• NP-hardness of Euclidean sum-of-squares clustering
• A randomized approximation scheme for metric MAX-CUT
• Machine Learning
• 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
• P-Complete Approximation Problems
• An Introduction to Statistical Learning
• Complexity of the weighted max-cut in Euclidean space

This page was built for publication: On the complexity of some quadratic Euclidean 2-clustering problems