Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters

DOI10.1134/S096554251911006XzbMath1451.62074OpenAlexW3014008886MaRDI QIDQ2206419

Alexander Kel'Manov, Vladimir Khandeev, Artem V. Pyatkin

Publication date: 22 October 2020

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

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

zbMATH Keywords

Euclidean spaceNP-completenessbalanced partitionquadratic variancesize-weighted variancevariance normalized by cluster size

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Uses Software

• ElemStatLearn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The planar \(k\)-means problem is NP-hard
• Data mining. Concepts and techniques
• NP-hardness of Euclidean sum-of-squares clustering
• Cluster analysis and mathematical programming
• Minimum sum of squares clustering in a low dimensional space
• Finding k points with minimum diameter and related problems
• A Best Possible Heuristic for the k-Center Problem
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem
• Data Mining
• The elements of statistical learning. Data mining, inference, and prediction