NP-hard approximation problems in overlapping clustering. (English) Zbl 1040.91084

Summary: We prove that the approximation of a dissimilarity by an indexed pseudo-hierarchy (also called a pyramid) or an indexed quasi-hierarchy (also called an indexed weak hierarchy) is an NP-hard problem for any \(L_p\)-norm \((p<\infty)\). These problems also correspond to the approximation by a strongly Robinson dissimilarity or by a dissimilarity fulfilling the four-point inequality. The results are extended to circular strongly Robinson dissimilarities, indexed \(k\)-hierarchies, and to proper dissimilarities satisfying the Bertrand and Janowitz \((k+ 2)\)-point inequality. Unidimensional scaling (linear or circular) is reinterpreted as a clustering problem and its hardness is established, but only for the \(L_1\) norm.


91C20 Clustering in the social and behavioral sciences
65Y20 Complexity and performance of numerical algorithms
91C15 One- and multidimensional scaling in the social and behavioral sciences