Norm statistics and the complexity of clustering problems (Q1026145)

For applications to clustering problems, some properties of weighted \(p\)-power means, called ``\(l_p\)-statistics'', \(p\geq1\), are considered first. Based on these generalized means, partitions \(B_1,\dots,B_m\) of a set of \(n>m\) scalar observations \(x_1,\dots,x_n\) are determined minimizing a weighted \(q\)-power mean criterion, where \(q\geq1\). Some properties of the resulting partitions, such as the ``string property'', known from standard clustering theory are transferred to the present case of power mean estimates. Moreover, the NP-hardness of the optimization problem for finding an optimal partition is discussed. An application is mentioned.