Clustering Problems Combining \(\ell p\)-statistics and \(\ell q\)-norms
Beth Novick – Clemson University, United States
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.