On the complexity of clustering with relaxed size constraints in fixed dimension
type: Item
instance of: scholarly article
title: On the complexity of clustering with relaxed size constraints in fixed dimension
zbMATH Open document ID: 1388.68116
author: Massimiliano Goldwurm
author: Jianyi Lin
author: Francesco Saccà
published in: Theoretical Computer Science
publication date: 2018-03-13T00:00:00Z
full work available at URL: http://hdl.handle.net/2434/565854
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 62H30
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 6849499
zbMATH Keywords: geometric clustering problems
zbMATH Keywords: cluster-size constraints
zbMATH Keywords: computational complexity
zbMATH Keywords: constrained \(k\)-means
Wikidata QID: Q59538782
describes a project that uses: PRMLT
MaRDI profile type: Publication
OpenAlex ID: W2622761779
cites work: NP-hardness of Euclidean sum-of-squares clustering
cites work: Size constrained distance clustering: separation properties and some complexity results
cites work: Q5483032
cites work: On Grouping for Maximum Homogeneity
cites work: On the Complexity of Clustering with Relaxed Size Constraints
cites work: The Problem of Compatible Representatives
cites work: Planar Formulae and Their Uses
cites work: Exact algorithms for size constrained 2-clustering in the plane
cites work: Least squares quantization in PCM
cites work: Computing and Combinatorics
cites work: Q5617409
cites work: The planar \(k\)-means problem is NP-hard
cites work: Minimum-weight triangulation is NP-hard
cites work: Q4217266
cites work: Cluster Analysis and Mathematical Programming
cites work: Cardinality constrained combinatorial optimization: complexity and polyhedra
cites work: Q4473284
cites work: \(k\)-means requires exponentially many iterations even in the plane
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: Integer Programming and the Theory of Grouping
DOI: 10.1016/J.TCS.2017.04.017
description: scientific article; zbMATH DE number 6849499