Two approximation algorithms for bipartite matching on multicore architectures

Fanny Dufossé 1 Kamer Kaya 2 Bora Uçar 3, 4
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, 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 a 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 under some common conditions. 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 very good scalability. We prove that this second heuristic has an approximation guarantee of around 0.866 under the same conditions as in the first algorithm. We discuss parallel implementations of the proposed heuristics on a multicore architecture. Experimental results, for demonstrating speed-ups and verifying the theoretical results in practice, are provided.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2015, 85, pp.62-78. 〈10.1016/j.jpdc.2015.06.009〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01242516
Contributeur : Equipe Roma <>
Soumis le : samedi 12 décembre 2015 - 20:52:57
Dernière modification le : mardi 16 janvier 2018 - 16:23:38
Document(s) archivé(s) le : samedi 29 avril 2017 - 11:58:02

Fichier

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

Identifiants

Citation

Fanny Dufossé, Kamer Kaya, Bora Uçar. Two approximation algorithms for bipartite matching on multicore architectures. Journal of Parallel and Distributed Computing, Elsevier, 2015, 85, pp.62-78. 〈10.1016/j.jpdc.2015.06.009〉. 〈hal-01242516〉

Partager

Métriques

Consultations de la notice

306

Téléchargements de fichiers

130