Clustering Problems Combining \(\ell p\)-statistics and \(\ell q\)-norms

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.