On the Complexity of Clustering with Relaxed Size Constraints

DOI10.1007/978-3-319-41168-2_3zbMath1476.68108OpenAlexW2505527801WikidataQ59538790 ScholiaQ59538790MaRDI QIDQ2830056

Francesco Saccà, Jianyi Lin, Massimiliano Goldwurm

Publication date: 9 November 2016

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycluster-size constraintsgeometric clustering problemsconstrained k-means

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

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

Uses Software

• PRMLT

Cites Work

• Unnamed Item
• 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 Grouping for Maximum Homogeneity
• 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