Size Constrained Distance Clustering: Separation Properties and Some Complexity Results

作者：Bertoni Alberto; Goldwurm Massimiliano; Lin Jianyi^*; Sacca Francesco

来源：Fundamenta Informaticae, 2012, 115(1): 125-139.

DOI：10.3233/FI-2012-644

• clustering
• size constraints
• NP-hardness

In this paper we study the complexity of some size constrained clustering problems with norm L-p. We obtain the following results: %26lt;br%26gt;(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 %26quot;String Property%26quot;; %26lt;br%26gt;(ii) The NP-hardness of the constrained 2-clustering problem for every norm L-p (p %26gt; 1); %26lt;br%26gt;(iii) A polynomial time algorithm for the constrained 2-clustering problem in dimension 1 for every norm L-p with integer p. We also give evidence that this result cannot be extended to norm L-p with rational non-integer p; %26lt;br%26gt;(iv) The NP-hardness of the constrained clustering problem in dimension 1 for every norm L-p (p %26gt;= 1).

• 出版日期2012