.png){kind=icon}
.png){kind=icon}
Return
EFFICIENT APPROXIMATION ALGORITHMS FOR WEIGHTED b-MATCHING
.png){kind=icon}
OA
AI
DOI：10.1137/15M1026304.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 well up to 240 threads on a shared-memory multiprocessor. The b-SUITOR algorithm outperforms the locally dominant edge algorithm by a factor of 14 on 16 cores of an Intel Xeon multiprocessor.
Keywords:
b-matching
approximation algorithms
parallel algorithms
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
View more organizations