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 L1-norm an analogous procedure known for the Euclidean norm. Moreover, we prove that in dimension 2, assuming Euclidean norm, the problem is (strongly) NP-hard with size constraints M={2, 4}. This result is extended also to the size constraints M={2, 3} both in the case of Euclidean and L1-norm.

On the complexity of clustering with relaxed size constraints in fixed dimension / M. Goldwurm, J. Lin, F. Saccà. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 717(2018 Mar 22), pp. 37-46. [10.1016/j.tcs.2017.04.017]

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

M. Goldwurm
Primo
;
J. Lin
;
2018-03-22

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 L1-norm an analogous procedure known for the Euclidean norm. Moreover, we prove that in dimension 2, assuming Euclidean norm, the problem is (strongly) NP-hard with size constraints M={2, 4}. This result is extended also to the size constraints M={2, 3} both in the case of Euclidean and L1-norm.
geometric clustering problems; cluster size constraints; computational complexity; constrained k-Means
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
relaxed-rivista9.pdf

embargo fino al 12/01/2019

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 229.88 kB
Formato Adobe PDF
229.88 kB Adobe PDF Visualizza/Apri
1-s2.0-S0304397517304619-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 2.62 MB
Formato Adobe PDF
2.62 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/565854
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact