Two approximation algorithms for bipartite matching on multicore architectures
详细信息 查看全文
- 作者：Fanny Dufossé ; a ; fanny.dufosse@inria.fr" class="auth_mail" title="E-mail the corresponding authorAuthor Vitae ; Kamer Kayab ; kaya@sabanciuniv.edu" class="auth_mail" title="E-mail the corresponding authorAuthor Vitae ; Bora Uç ; arc ; bora.ucar@ens-lyon.fr" class="auth_mail" title="E-mail the corresponding authorAuthor Vitae
- 关键词：Shared memory parallelism ; Matching ; Bipartite graphs ; Approximation algorithm
- 刊名：Journal of Parallel and Distributed Computing
- 出版年：2015
- 出版时间：November 2015
- 年：2015
- 卷：85
- 期：Complete
- 页码：62-78
- 全文大小：2108 K
文摘
- •
We propose two parallel approximation algorithms for bipartite matching.
- •
The first algorithm is cheaper and has an approximation ratio of around 0.632.
- •
The second algorithm has an approximation ratio of around 0.866.
- •
The parallel performances of the algorithms are analyzed.
- •
The algorithms scale well on a multi-core architecture and various graphs.