Bipartite Matching Heuristics with Quality Guarantees on Shared Memory Parallel Computers

Fanny Dufossé 1 Kamer Kaya 2 Bora Uçar 3, 4
1 LAAS-TSF - Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
2 Department of Biomedical Informatics [Columbus]
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We propose two heuristics for the bipartite matching problem that are amenable to shared-memory parallelization. The first heuristic is very intriguing from parallelization perspective. It has no significant algorithmic synchronization overhead and no conflict resolution is needed across threads. We show that this heuristic has an approximation ratio of around 0.632. The second heuristic is designed to obtain a larger matching by employing the well-known Karp-Sipser heuristic on a judiciously chosen subgraph of the original graph. We show that the Karp-Sipser heuristic always finds a maximum cardinality matching in the chosen subgraph. Although the Karp-Sipser heuristic is hard to parallelize for general graphs, we exploit the structure of the selected subgraphs to propose a specialized implementation which demonstrates a very good scalability. Based on our experiments and theoretical evidence, we conjecture that this second heuristic obtains matchings with cardinality of at least 0.866 of the maximum cardinality. We discuss parallel implementations of the proposed heuristics on shared memory systems. Experimental results, for demonstrating speed-ups and verifying the theoretical results in practice, are provided.
Keywords : Bipartite graph cardinality matching approximation algorithm shared memory programming
Type de document :
Communication dans un congrès
28th IEEE International Parallel & Distributed Processing Symposium (IPDPS), May 2014, Phoenix, Arizona, United States. 2014, 〈10.1109/IPDPS.2014.63〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01235162
Contributeur : Equipe Roma <>
Soumis le : samedi 28 novembre 2015 - 16:29:10
Dernière modification le : vendredi 9 novembre 2018 - 01:19:58
Document(s) archivé(s) le : samedi 29 avril 2017 - 00:37:45

Fichier

oneOutMatching.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INSMI | LIP | INRIA | ENS-LYON | UNIV-TLSE3 | INSA-TOULOUSE | TDS-MACS | UNIV-LYON1 | LAAS-TSF | LAAS-INFORMATIQUE-CRITIQUE | LAAS

Citation

Fanny Dufossé, Kamer Kaya, Bora Uçar. Bipartite Matching Heuristics with Quality Guarantees on Shared Memory Parallel Computers. 28th IEEE International Parallel & Distributed Processing Symposium (IPDPS), May 2014, Phoenix, Arizona, United States. 2014, 〈10.1109/IPDPS.2014.63〉. 〈hal-01235162〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

496

Téléchargements de fichiers

128

Contact


archive-ouverte@inria.fr