A branch and bound method for the aggregation of symmetric relations

Abstract :

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.

Complete list of metadatas

https://hal.telecom-paristech.fr/hal-02286302
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 3:35:13 PM
Last modification on : Thursday, October 17, 2019 - 12:37:00 PM

Identifiers

  • HAL Id : hal-02286302, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

10