Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability

DOI10.1134/S0081543821030123OpenAlexW3183214496WikidataQ114075159 ScholiaQ114075159MaRDI QIDQ2043627

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

Publication date: 3 August 2021

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

clusteringcenterEuclidean spacemedianquadratic variationstrong NP-hardnesscentroid2-partitionapproximation-preserving reductionnonexistence of FPTAS

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Uses Software

• PRMLT

Cites Work

• NP-hardness of Euclidean sum-of-squares clustering
• A randomized algorithm for two-cluster partition of a set of vectors
• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability