Bipartite matching heuristics with quality guarantees on shared memory parallel computers

Résumé : Cet article étudie le problème de couplage dans des graphes bipartis et propose deux heuristiques adaptées à une parallélisation dans un contexte de mémoire partagée. La première heuristique est particulièrement intéressante du point de vue du parallélisme. Sa parallélisation ne cause aucun surcoût lié à des synchronisations, ni aucun conflit mémoire. Nous montrons que cette heuristique approche le couplage maximal d'un ratio d'environ 0,632. La seconde heuristique utilise l'heuristique de Karp-Sipser sur un sous-graphe judicieusement choisi du graphe original. Nous montrons que l'algorithme de Karp-Sipser obtient toujours le couplage maximal pour le sous-graphe considéré. Cet algorithme n'est que difficilement parallélisable dans le cas général, mais la structure particulière des sous-graphes considérés nous permet de proposer une implémentation adaptée à une exécution parallèle. Nous conjecturons que cette seconde heuristique approche le couplage maximal d'un ratio d'environ 0,866. Nous abordons les possibles implémentations parallèles de ces heuristiques sur un système à mémoire partagée. Des résultats expérimentaux montrent l'accélération du calcul due à l'exécution parallèle et confirment dans la pratique les résultat théoriques.
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00877211
Contributeur : Equipe Roma <>
Soumis le : lundi 7 juillet 2014 - 09:45:46
Dernière modification le : mardi 16 janvier 2018 - 15:36:20
Document(s) archivé(s) le : mardi 11 avril 2017 - 09:44:51

Fichier

RR-8386.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00877211, version 3

Citation

Fanny Dufossé, Kamer Kaya, Bora Uçar. Bipartite matching heuristics with quality guarantees on shared memory parallel computers. [Research Report] Inria; laas. 2013, pp.28. 〈hal-00877211v3〉

Partager

Métriques

Consultations de la notice

429

Téléchargements de fichiers

186