Information theoretical clustering is hard to approximate

An impurity measures I: ℝd mapsto ℝ^+ is a function that assigns a d-dimensional vector bf v to a non-negative value I(bf v) so that the more homogeneous bf v, with respect to the values of its coordinates, the larger its impurity. A well known example of impurity measures is the Entropy impurity. We study the problem of clustering based on impurity measures. Let V be a collection of n many d-dimensional vectors with non-negative components. Given V and an impurity measure I, the goal is to find a partition mathcal P of V into k groups V1,ldots,Vk so as to minimize the sum of the impurities of the groups in cal P, i.e., I(cal P)= sumi=1k Ibigg(sum_ bf v ∈ Vi bf v bigg). Impurity minimization has been widely used as quality assessment measure in probability distribution clustering (KL-divergence) as well as in categorical clustering. However, in contrast to the case of metric based clustering, the current knowledge of impurity measure based clustering in terms of approximation and inapproximability results is very limited. Here, we contribute to change this scenario by proving that for the Entropy impurity measure the problem does not admit a PTAS even when all vectors have the same ℓ1 norm. This result solves a question that remained open in previous work on this topic [Chaudhuri and McGregor COLT 08; Ackermann et. al. ECCC 11].