On the complexity of clustering with relaxed size constraints in fixed dimension

DOI10.1016/j.tcs.2017.04.017zbMath1388.68116OpenAlexW2622761779WikidataQ59538782 ScholiaQ59538782MaRDI QIDQ1704856

Francesco Saccà, Jianyi Lin, Massimiliano Goldwurm

Publication date: 13 March 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2434/565854

zbMATH Keywords

computational complexitycluster-size constraintsconstrained \(k\)-meansgeometric clustering problems

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Uses Software

• PRMLT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms for size constrained 2-clustering in the plane
• Cardinality constrained combinatorial optimization: complexity and polyhedra
• The planar \(k\)-means problem is NP-hard
• \(k\)-means requires exponentially many iterations even in the plane
• NP-hardness of Euclidean sum-of-squares clustering
• On the Complexity of Clustering with Relaxed Size Constraints
• On Grouping for Maximum Homogeneity
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Minimum-weight triangulation is NP-hard
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Least squares quantization in PCM
• Integer Programming and the Theory of Grouping
• Cluster Analysis and Mathematical Programming
• Computing and Combinatorics