Combinatorial optimization and hierarchical classifications |
| |
Authors: | Email author" target="_blank">Jean-Pierre?BarthélemyEmail author Fran?ois?Brucker Christophe?Osswald |
| |
Institution: | (1) ENST Bretagne, Deptartments de LUSSI et TAMCIC, FRE CNRS 2658, BP 832, 29285 Brest cedex, France;(2) Laboratoire E3I2, ENSIETA, France;(3) CAMS, EHESS, UMR CNRS 8557, 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.Received: July 2004, Revised: September 2004, MSC classification:
62H30, 91C20, 05C65, 90C27, 68R01 |
| |
Keywords: | Hierarchical classification quasi-hierarchies rigid hypergraphs complexity clustering algorithms subdominant |
本文献已被 SpringerLink 等数据库收录! |
|