Group for Research in Decision Analysis

G-95-29

Computational Methods in Clustering from a Mathematical Programming Viewpoint

and

Cluster Analysis is at the crossroad of many disciplines, and has numerous and diverse methods and applications. Mathematical Programming (together with graph theory, complexity theory and data structures) can be used to give a coherent view of the field. This leads to define clustering paradigms, specify problems within these paradigms as mathematical programs, study their complexity, design polynomial algorithms for easy problems, non polynomial ones or heuristics for hard ones and evaluate results obtained. An overview of this line of research is given, stressing exact algorithms.

, 23 pages

This cahier was revised in August 1995