Norm statistics and the complexity of clustering problems

In this paper we introduce a new class of clustering problems. These are similar to certain classical problems but involve a novel combination of ℓpℓp-statistics and ℓqℓq norms. We discuss a real world application in which the case p=2p=2 and q=1q=1 arises in a natural way. We show that, even for one dimension, such problems are NP-hard, which is surprising because the same 1-dimensional problems for the ‘pure’ ℓ2ℓ2-statistic and ℓ2ℓ2 norm are known to satisfy a ‘string property’ and can be solved in polynomial time. We generalize the string property for the case p=qp=q. The string property need not   hold when q≤p−1q≤p−1 and we show that instances may be constructed, for which the best solution satisfying the string property does arbitrarily poorly. We state some open problems and conjectures.