Groupe d’études et de recherche en analyse des décisions

# Clustering Problems Combining $$\ell p$$-statistics and $$\ell q$$-norms

## Beth Novick – Clemson University, États-Unis

We discuss a class of clustering problems that are similar to certain classical problems but involve a novel combination of $$\ell p$$-statistics and $$\ell q$$-norms. In this talk we focus on the complexity of these problems and on a heuristic solution technique. Even for one dimension, such problems are NP-hard, which is surprising because the same 1-dimensional problems for the "pure" $$\ell 2$$-statistic and $$\ell 2$$-norm are known to satisfy a "string property" and can be solved in polynomial time. We generalize the string property for the case where $$p$$ is equal to $$q$$. We give a counterexample showing that the string property need not hold when $$q$$ is smaller than p and show that instances may be constructed for which the best solution satisfying the string property does arbitrarily poorly. We discuss a real world application in which the case "$$p=2$$ and $$q=1$$" arises in a natural way. We give a neighborhood search heuristic for this application that uses both random and "intelligent" starting solutions and give some preliminary computational results.