Combinatorial optimisation and hierarchical classifications |
| |
Authors: | J-P Barthélemy F Brucker C Osswald |
| |
Institution: | (1) CAMS, EHESS, UMR CNRS 8557, Paris, France;(2) ENST Bretagne, Dept. LUSSI and TAMCIC, FRE CNRS 2658, Paris, France;(3) ENSIETA, Laboratoire E3I2, Paris, France |
| |
Abstract: | This paper is devoted to some selected topics relating Combinatorial Optimization and Hierarchical Classification. It is oriented
toward extensions of the standard classification schemes (the hierarchies): pyramids, quasi-hierarchies, circular clustering,
rigid clustering and others. Bijection theorems between these models and dissimilarity models allow to state some clustering
problems as optimization problems. Within the galaxy of optimization we have especially discussed the following: NP-completeness
results and search for polynomial instances; problems solved in a polynomial time (e.g. subdominant theory); design, analysis
and applications of algorithms. In contrast with the orientation to “new” clustering problems, the last part discusses some
standard algorithmic approaches.
This article appeared in 4OR 2, 179–219, 2004. |
| |
Keywords: | Hierarchical classification Quasi-hierarchies Rigid hypergraphs Complexity Clustering algorithms Subdominant |
本文献已被 SpringerLink 等数据库收录! |
|