Efficient Approximation Algorithms for Weighted $b$-Matching
| Autor: | Fredrik Manne, Arif O. Khan, Mahantesh Halappanavar, Pradeep Dubey, Md. Mostofa Ali Patwary, Narayanan Sundaram, Nadathur Satish, Alex Pothen |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Vertex (graph theory)
Applied Mathematics Parallel algorithm Approximation algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics Minimum k-cut Computational Mathematics 010201 computation theory & mathematics Kruskal's algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Multiple edges Greedy algorithm MathematicsofComputing_DISCRETEMATHEMATICS Hopcroft–Karp algorithm Mathematics |
| Zdroj: | SIAM Journal on Scientific Computing. 38:S593-S619 |
| ISSN: | 1095-7197 1064-8275 |
| DOI: | 10.1137/15m1026304 |
| Popis: | We describe a half-approximation algorithm, $b$-Suitor, for computing a $b$-Matching of maximum weight in a graph with weights on the edges. $b$-Matching is a generalization of the well-known Matching problem in graphs, where the objective is to choose a subset of $M$ edges in the graph such that at most a specified number $b(v)$ of edges in $M$ are incident on each vertex $v$. Subject to this restriction we maximize the sum of the weights of the edges in $M$. We prove that the $b$-Suitor algorithm computes the same $b$-Matching as the one obtained by the Greedy algorithm for the problem. We implement the algorithm on serial and shared-memory parallel processors and compare its performance against a collection of approximation algorithms that have been proposed earlier. Our results show that the $b$-Suitor algorithm outperforms the Greedy and locally dominant edge algorithms by one to two orders of magnitude on a serial processor. The $b$-Suitor algorithm has a high degree of concurrency, and it scales we... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|