Published in

IOS Press, Fundamenta Informaticae, 1(115), p. 125-139, 2012

DOI: 10.3233/fi-2012-644

Links

Tools

Export citation

Search in Google Scholar

Size Constrained Distance Clustering: Separation Properties and Some Complexity Results

Journal article published in 2012 by Alberto Bertoni, Massimiliano Goldwurm, Jianyi Lin, Francesco Saccà
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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