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

DOI10.1016/J.TCS.2017.04.017MaRDI QIDQ1704856zbMATH OpenOpenAlexWikidataFDO

Authors Massimiliano Goldwurm, Jianyi Lin, Francesco Saccà

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

cluster-size constraintscomputational complexityconstrained \(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)

Recommendations

• On the Complexity of Clustering with Relaxed Size Constraints
• Size constrained distance clustering: separation properties and some complexity results
• Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability
• NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes
• On the complexity of some quadratic Euclidean 2-clustering problems

Cites work

• k-means requires exponentially many iterations even in the plane
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Cardinality constrained combinatorial optimization: complexity and polyhedra
• Cluster Analysis and Mathematical Programming
• Computing and Combinatorics
• Exact algorithms for size constrained 2-clustering in the plane
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 2080486 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• Integer Programming and the Theory of Grouping
• Least squares quantization in PCM
• Minimum-weight triangulation is NP-hard
• NP-hardness of Euclidean sum-of-squares clustering
• On Grouping for Maximum Homogeneity
• On the Complexity of Clustering with Relaxed Size Constraints
• Pattern recognition and machine learning.
• Planar Formulae and Their Uses
• Size constrained distance clustering: separation properties and some complexity results
• The planar \(k\)-means problem is NP-hard
• The Problem of Compatible Representatives

Cited in

(8)

• Parameterized \(k\)-clustering: tractability island
• On the Complexity of Clustering with Relaxed Size Constraints
• Size constrained distance clustering: separation properties and some complexity results
• Exact algorithms for size constrained 2-clustering in the plane
• On the complexity of some cluster analysis problems
• scientific article; zbMATH DE number 2011857 (Why is no real title available?)
• scientific article; zbMATH DE number 7378621 (Why is no real title available?)
• On the hardness of labeled correlation clustering problem: a parameterized complexity view

Describes a project that uses

Uses Software

• PRMLT

This page was built for publication: On the complexity of clustering with relaxed size constraints in fixed dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704856)