@inproceedings{
 title = {On the complexity of clustering with relaxed size constraints},
 type = {inproceedings},
 year = {2016},
 keywords = {Cluster size constraints,Computational complexity,Constrained k-means,Geometric clustering problems},
 pages = {26-38},
 volume = {9778},
 id = {57ba69dd-92a7-36f9-ac4e-5465322fc0ea},
 created = {2020-05-28T13:59:34.340Z},
 file_attached = {false},
 profile_id = {6bce6ab9-03b5-36ad-a474-26e482dc52c3},
 last_modified = {2020-05-28T14:08:01.198Z},
 read = {false},
 starred = {false},
 authored = {true},
 confirmed = {true},
 hidden = {false},
 private_publication = {false},
 abstract = {We study the computational complexity of the problem of computing an optimal clustering A1, A2, …,Ak of a set of points assuming that every cluster size |Ai| belongs to a given set M of positive integers. We present a polynomial time algorithm for solving the problem in dimension 1, i.e. when the points are simply rational values, for an arbitrary set M of size constraints, which extends to the ℓ1-norm an analogous procedure known for the ℓ2-norm. Moreover, we prove that in the Euclidean plane, i.e. assuming dimension 2 and ℓ2-norm, the problem is NP-hard even with size constraints set reduced to M = 2, 3.},
 bibtype = {inproceedings},
 author = {Goldwurm, Massimiliano and Lin, Jianyi and Saccà, Francesco},
 doi = {10.1007/978-3-319-41168-23},
 booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}
}

{"_id":"G4wGYyvzqBZZtfMfD","bibbaseid":"goldwurm-lin-sacc-onthecomplexityofclusteringwithrelaxedsizeconstraints-2016","authorIDs":["EF82ixfaSgYFdM2FT"],"author_short":["Goldwurm, M.","Lin, J.","Saccà, F."],"bibdata":{"title":"On the complexity of clustering with relaxed size constraints","type":"inproceedings","year":"2016","keywords":"Cluster size constraints,Computational complexity,Constrained k-means,Geometric clustering problems","pages":"26-38","volume":"9778","id":"57ba69dd-92a7-36f9-ac4e-5465322fc0ea","created":"2020-05-28T13:59:34.340Z","file_attached":false,"profile_id":"6bce6ab9-03b5-36ad-a474-26e482dc52c3","last_modified":"2020-05-28T14:08:01.198Z","read":false,"starred":false,"authored":"true","confirmed":"true","hidden":false,"private_publication":false,"abstract":"We study the computational complexity of the problem of computing an optimal clustering A1, A2, …,Ak of a set of points assuming that every cluster size |Ai| belongs to a given set M of positive integers. We present a polynomial time algorithm for solving the problem in dimension 1, i.e. when the points are simply rational values, for an arbitrary set M of size constraints, which extends to the ℓ1-norm an analogous procedure known for the ℓ2-norm. Moreover, we prove that in the Euclidean plane, i.e. assuming dimension 2 and ℓ2-norm, the problem is NP-hard even with size constraints set reduced to M = 2, 3.","bibtype":"inproceedings","author":"Goldwurm, Massimiliano and Lin, Jianyi and Saccà, Francesco","doi":"10.1007/978-3-319-41168-23","booktitle":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","bibtex":"@inproceedings{\n title = {On the complexity of clustering with relaxed size constraints},\n type = {inproceedings},\n year = {2016},\n keywords = {Cluster size constraints,Computational complexity,Constrained k-means,Geometric clustering problems},\n pages = {26-38},\n volume = {9778},\n id = {57ba69dd-92a7-36f9-ac4e-5465322fc0ea},\n created = {2020-05-28T13:59:34.340Z},\n file_attached = {false},\n profile_id = {6bce6ab9-03b5-36ad-a474-26e482dc52c3},\n last_modified = {2020-05-28T14:08:01.198Z},\n read = {false},\n starred = {false},\n authored = {true},\n confirmed = {true},\n hidden = {false},\n private_publication = {false},\n abstract = {We study the computational complexity of the problem of computing an optimal clustering A1, A2, …,Ak of a set of points assuming that every cluster size |Ai| belongs to a given set M of positive integers. We present a polynomial time algorithm for solving the problem in dimension 1, i.e. when the points are simply rational values, for an arbitrary set M of size constraints, which extends to the ℓ1-norm an analogous procedure known for the ℓ2-norm. Moreover, we prove that in the Euclidean plane, i.e. assuming dimension 2 and ℓ2-norm, the problem is NP-hard even with size constraints set reduced to M = 2, 3.},\n bibtype = {inproceedings},\n author = {Goldwurm, Massimiliano and Lin, Jianyi and Saccà, Francesco},\n doi = {10.1007/978-3-319-41168-23},\n booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}\n}","author_short":["Goldwurm, M.","Lin, J.","Saccà, F."],"biburl":"https://bibbase.org/service/mendeley/6bce6ab9-03b5-36ad-a474-26e482dc52c3","bibbaseid":"goldwurm-lin-sacc-onthecomplexityofclusteringwithrelaxedsizeconstraints-2016","role":"author","urls":{},"keyword":["Cluster size constraints","Computational complexity","Constrained k-means","Geometric clustering problems"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"inproceedings","biburl":"https://bibbase.org/service/mendeley/6bce6ab9-03b5-36ad-a474-26e482dc52c3","creationDate":"2020-05-28T13:51:27.023Z","downloads":0,"keywords":["cluster size constraints","computational complexity","constrained k-means","geometric clustering problems"],"search_terms":["complexity","clustering","relaxed","size","constraints","goldwurm","lin","saccà"],"title":"On the complexity of clustering with relaxed size constraints","year":2016,"dataSources":["KrZZ3KEZ3zvS84wws","ya2CyA73rpZseyrZ8","2252seNhipfTmjEBQ"]}