NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes

DOI10.1134/S1064562419060127zbMath1452.68084OpenAlexW4240963999MaRDI QIDQ2191318

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

Publication date: 24 June 2020

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

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

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems

Uses Software

• PRMLT

Cites Work

• NP-hardness of Euclidean sum-of-squares clustering
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Introduction to Statistical Learning
• Data Mining
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes