Article
Full entry |
PDF
(0.9 MB)
Feedback
PDF
(0.9 MB)
Feedback
Keywords:
hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; $k$-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete
hierarchical overlapping clustering; computational complexity; approximation of a given dissimilarity measure; $k$-ultrametric; Robinson dissimilarity measure; decision problems; NP-complete
Summary:
In this paper the computational complexity of the problem of the approximation of a given dissimilarity measure on a finite set $X$ by a $k$-ultrametric on $X$ and by a Robinson dissimilarity measure on $X$ is investigared. It is shown that the underlying decision problems are NP-complete.
References:
[1] E. Diday: Une représentation visuelle des classes empiétantes - les pyramides. Rap. de Recherche No 291, INRIA, Rocquencourt, 1984.
[2] M. R. Garey, D. S. Johnson: Computers and Intractability: a Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco, 1979. MR 0519066 | Zbl 0411.68039
[3] L. Hubert: A set-theoretical approach to the problem of hierarchical clustering. Journal of Mathematical Psychology, 15 (1977), 1 pp. 70--88. DOI 10.1016/0022-2496(77)90041-4 | MR 0527187 | Zbl 0358.62042
[4] N. Jardine, R. Sibson: Mathematical Taxonomy. Wiley, London, 1971. MR 0441395 | Zbl 0322.62065
[5] R. M. Karp: Red liability among combinatorial problems. Complexity of computer computations, Proceedings, Plenum Press 1972. Editors: R. E. Miller, J. W. Thatcher. MR 0373375
[6] M. Křivánek, J. Morávek: On NP-hardness in hierarchical clustering. COMPSTAT 1984, Proceedings, Physica-Verlag 1984. Editors: T. Havránek, Z. Šidák, M. Novák. MR 0806995
Search
Partner of
