Two approximation algorithms for bipartite matching on multicore architectures
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.
approximation algorithm matching shared memory parallelism bipartite graphs