NP-hard Approximation Problems in Overlapping Clustering
NP-hard Approximation Problems in Overlapping Clustering
复制标题
重叠聚类中的 NP 困难近似问题
DOI：
--
复制
发表时间：
2001
影响因子：
2
通讯作者：
François Brucker
中科院分区：
文献类型：
--
作者：
J. Barthélemy;François Brucker
Lp-范数（p < ∞）。这些问题也对应于强罗宾逊相异度或满足四点不等式的相异度的近似（Bandelt 1992; Diatta and Fichet 1994）。结果被推广到循环强罗宾逊相异，索引k-层次（Jardine和Sibson 1971，pp. 65-71），以及满足Bertrand和Janowitz（k + 2）点不等式的适当相异度（Bertrand和Janowitz 1999）。一维尺度（线性或圆形）被重新解释为聚类问题，并建立其硬度，但仅适用于L1范数。
L p-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 L1 norm.