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

Barthélemy, Jean-Pierre; Brucker, François

J. Classif. 18, No. 2, 159-183 (2001).

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

Keywords:

approximation problems; complexity; pseudo-hierarchies; \(k\)-hierarchies; \(k\)-weak hierarchies; Robinson dissimilarities