A branch and bound method for the aggregation of symmetric relations - Département Informatique et Réseaux Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

A branch and bound method for the aggregation of symmetric relations

Résumé

We consider the problem of the aggregation of symmetric relations into a median equivalence relation, with in particular two spe- cial cases: the one for which the symmetric relations are equivalence relations (Régnier's problem), and the one of the approximation of one symmetric relation by an equivalence relation (Zahn's problem). These problems arise for instance from the field of classication or clustering, when one wants to gather objects in such a way that the objects of any cluster can be considered as similar, while the objects of different clusters can be considered as dissimilar. We first state this problem as a clique partitioning problem in graph theory. As this problem is NP-hard, we then design a branch and bound algorithm to solve this problem, based on a Lagrangean relaxation method for the evaluation function and on noising methods for the initial bound.
Fichier non déposé

Dates et versions

hal-02286302 , version 1 (13-09-2019)

Identifiants

  • HAL Id : hal-02286302 , version 1

Citer

Irène Charon, Olivier Hudry. A branch and bound method for the aggregation of symmetric relations. 2nd International Symposium on Combinatorial Optimization (ISCO 2012), Apr 2012, Athènes, Greece. pp.127-130. ⟨hal-02286302⟩
45 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More