06033542

j

06033542 Bertoni, Alberto Goldwurm, Massimiliano Lin, Jianyi Sacc\`a, Francesco Size constrained distance clustering: separation properties and some complexity results. Fundam. Inform. 115, No. 1, 125-139 (2012). 2012 Polish Mathematical Society, Warsaw; IOS Press, Amsterdam EN clustering size constraints NP-hardness

http://iospress.metapress.com/content/ph720t2kq50h6q77/fulltext.html

Summary: We study the complexity of some size constrained clustering problems with norm $L_p$. 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 $L_p$ ($p > 1$); (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$; (iv) The NP-hardness of the constrained clustering problem in dimension 1 for every norm $L_p$ ($p \geq 1$).