Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

An efficient algorithm for computing the distance between close partitions

Abstract :

A K -partition of a set S is a splitting of S into K non-overlapping classes that cover all elements of S . Numerous practical applications dealing with data partitioning or clustering require computing the distance between two partitions. Previous articles proved that one can compute it in polynomial time—minimum O ( | S | + K 2 ) and maximum O ( | S | + K 3 ) —using a reduction to the linear assignment problem. We propose several conditions for which the partition distance can be computed in O ( | S | ) time. In practical terms, this computation can be done in O ( | S | ) time for any two relatively resembling partitions (i.e. with distance less than | S | 5 ) except specially constructed cases. Finally, we prove that, even if there is a bounded number of classes for which the proposed conditions are not satisfied, one can still preserve the linear complexity by exploiting decomposition properties of the similarity matrix.

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255391
Contributeur : Okina Université d'Angers <>
Soumis le : mercredi 9 juin 2021 - 15:04:24
Dernière modification le : jeudi 10 juin 2021 - 03:39:57

Identifiants

Collections

Citation

Daniel Cosmin Porumbel, Jin-Kao Hao, Pascale Kuntz. An efficient algorithm for computing the distance between close partitions. Discrete Applied Mathematics, Elsevier, 2011, 159 (1), pp.53 - 59. ⟨10.1016/j.dam.2010.09.002⟩. ⟨hal-03255391⟩

Partager

Métriques

Consultations de la notice

3