NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters

DOI10.1134/S1064562419050028zbMath1437.62232OpenAlexW2986153947WikidataQ126788242 ScholiaQ126788242MaRDI QIDQ2304346

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

Publication date: 11 March 2020

Published in: Doklady Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

partitioningNP-completenessclusterscluster sizeintracluster quadratic varianceset of points in Euclidean space

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Statistics on metric spaces (62R20)

Cites Work

• Unnamed Item
• Unnamed Item
• NP-hardness of Euclidean sum-of-squares clustering
• Finding k points with minimum diameter and related problems
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem