In this paper we study the complexity of some size constrained clustering problems with norm Lp. We obtain the following results: (i) A separation property for the constrained 2-clustering problem. This implies that the optimal solutions in the 1-dimensional case verify the so-called “String Property”; (ii) The NP-hardness of the constrained 2-clustering problem for every norm Lp (p > 1); (iii) A polynomial time algorithm for the constrained 2-clustering problem in dimension 1 for every norm Lp with integer p. We also give evidence that this result cannot be extended to norm Lp with rational non-integer p; (iv) The NP-hardness of the constrained clustering problem in dimension 1 for every norm Lp (p ≥ 1).

Size constrained distance clustering : separation properties and some complexity results / A. Bertoni, M. Goldwurm, J. Lin, F. Saccà. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 115:1(2012), pp. 125-139. [10.3233/FI-2012-644]

Size constrained distance clustering : separation properties and some complexity results

A. Bertoni
Primo
;
M. Goldwurm
Secondo
;
J. Lin
Penultimo
;
F. Saccà
Ultimo
2012

Abstract

In this paper we study the complexity of some size constrained clustering problems with norm Lp. We obtain the following results: (i) A separation property for the constrained 2-clustering problem. This implies that the optimal solutions in the 1-dimensional case verify the so-called “String Property”; (ii) The NP-hardness of the constrained 2-clustering problem for every norm Lp (p > 1); (iii) A polynomial time algorithm for the constrained 2-clustering problem in dimension 1 for every norm Lp with integer p. We also give evidence that this result cannot be extended to norm Lp with rational non-integer p; (iv) The NP-hardness of the constrained clustering problem in dimension 1 for every norm Lp (p ≥ 1).
clustering; NP-hardness; size constraints
Settore INF/01 - Informatica
2012
Article (author)
File in questo prodotto:
File Dimensione Formato  
fund_inf12.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 121.04 kB
Formato Adobe PDF
121.04 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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: https://hdl.handle.net/2434/190485
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 14
social impact