Two approximation algorithms for bipartite ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
Two approximation algorithms for bipartite matching on multicore architectures
Auteur(s) :
Dufossé, Fanny [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Kaya, Kamer [Auteur]
Department of Biomedical Informatics [Columbus]
Uçar, Bora [Auteur]
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Laboratoire de l'Informatique du Parallélisme [LIP]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Kaya, Kamer [Auteur]
Department of Biomedical Informatics [Columbus]
Uçar, Bora [Auteur]
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Laboratoire de l'Informatique du Parallélisme [LIP]
Titre de la revue :
Journal of Parallel and Distributed Computing
Pagination :
62-78
Éditeur :
Elsevier
Date de publication :
2015
ISSN :
0743-7315
Mot(s)-clé(s) en anglais :
shared memory parallelism
matching
bipartite graphs
approximation algorithm
matching
bipartite graphs
approximation algorithm
Discipline(s) HAL :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]/Mathématique discrète [cs.DM]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Mathématique discrète [cs.DM]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-01242516/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01242516/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01242516/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- randMatch.pdf
- Accès libre
- Accéder au document
- randMatch.pdf
- Accès libre
- Accéder au document