Question

Converge without partioning in optimization case means

Answer 1

Answer:

Clustering is an NP-complete problem - see proof fo the one definition of clustering and another definition of clustering.

The question of whether P=NP wasn't answered yet but is seems as if the complexity classes are different.

If it is so, then no polynomial time algorithm, like the pam algorithm can solve the problem.

When facing an NP-complete problem we can cope with it by looking for approximation algorithms. The one bellow has approximation ratio of 2.