Name
Title | ||
|---|---|---|
An auction-based weighted matching implementation on massively parallel architectures |
Abstract | ||
|---|---|---|
Maximum weighted matchings represent a fundamental kernel in massive graph analysis and occur in a wide range of real-life applications. Here, a parallel auction-based matching algorithm is developed, which is able to tackle matchings in very large, dense, and sparse bipartite graphs. It will be demonstrated that the convergence of the auction algorithm crucially depends on two different @e-scaling strategies. The auction algorithm including the @e-scaling strategies has been implemented using a hybrid MPI-OpenMP programming model, and its performance is validated in various applications from bioinformatics, computer vision, and sparse linear algebra. It is concluded that for dense bipartite graphs, the auction algorithm scales well, and for sparse bipartite graphs at least a substantial speedup is achieved against alternative approaches that are based on augmenting path algorithms. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.parco.2012.09.001 | Parallel Computing |
Keywords | Field | DocType |
auction algorithm,parallel auction-based matching algorithm,auction algorithm crucially,auction-based weighted matching implementation,maximum weighted matchings,sparse linear algebra,dense bipartite graph,parallel architecture,sparse bipartite graph,augmenting path algorithm,auction algorithm scale,e-scaling strategy,performance studies | Computer science,Massively parallel,Parallel computing,Bipartite graph,Hopcroft–Karp algorithm,Theoretical computer science,Assignment problem,3-dimensional matching,Auction algorithm,Blossom algorithm,Speedup | Journal |
Volume | Issue | ISSN |
38 | 12 | 0167-8191 |
Citations | PageRank | References |
9 | 0.59 | 25 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Madan Sathe | 1 | 33 | 2.41 |
| Olaf Schenk | 2 | 536 | 39.02 |
| Helmar Burkhart | 3 | 304 | 42.97 |