NP-hard Approximation Problems in Overlapping Clustering |
| |
Authors: | Jean-Pierre Barthélemy François Brucker |
| |
Institution: | (1) ENST Bretagne, France, |
| |
Abstract: | Lp
-norm (p < ∞). These problems also correspond to the approximation by a strongly Robinson dissimilarity or by a dissimilarity fulfilling
the four-point inequality (Bandelt 1992; Diatta and Fichet 1994). The results are extended to circular strongly Robinson dissimilarities,
indexed k-hierarchies (Jardine and Sibson 1971, pp. 65-71), and to proper dissimilarities satisfying the Bertrand and Janowitz (k + 2)-point inequality (Bertrand and Janowitz 1999). Unidimensional scaling (linear or circular) is reinterpreted as a clustering
problem and its hardness is established, but only for the L
1 norm. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|