## 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.

### MSC:

 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