Affiliations: Department of Computer Science, University of Milan, Via Comelico 39/41, 20135 Milan, Italy. {bertoni,goldwurm}@dsi.unimi.it; {jianyi.lin,francesco.sacca}@unimi.it
Note: [] Also works: Department of Mathematics, University of Milan, Milan, Italy Address for correspondence: Department of Computer Science, University of Milan, Via Comelico 39/41, 20135 Milan, Italy
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).
