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}.

On the complexity of clustering with relaxed size constraints / M. Goldwurm, J. Lin, F. Saccà - In: Algorithmic Aspects in Information and Management / [a cura di] R. Dondi, G. Fertin, G. Mauri. - Prima edizione. - Svizzera : Springer, 2016. - ISBN 9783319411675. - pp. 26-38 (( Intervento presentato al 11. convegno AAIM tenutosi a Bergamo nel 2016.

On the complexity of clustering with relaxed size constraints

M. Goldwurm;J. Lin;
2016

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}.
Cluster size constraints; Computational complexity; Constrained k-means; Geometric clustering problems
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
aaim-8.pdf

accesso aperto

Descrizione: Articolo
Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 196.15 kB
Formato Adobe PDF
196.15 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/426429
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact