.png){kind=icon}
返回
EFFICIENT APPROXIMATION ALGORITHMS FOR WEIGHTED b-MATCHING
.png){kind=icon}
OA
AI
DOI：10.1137/15M1026304.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
b-matching
approximation algorithms
parallel algorithms
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
2.6
论文数:
5.1K
被引数:
1.8W
机构
引用论文
Symmetrical discrimination despite weak song differentiation in 2 suboscine bird sister species尽管在2个亚科鸟类姊妹物种中歌曲分化较弱，但仍具有对称性歧视
.png){kind=icon}
PREAI
分享收藏分享收藏分享收藏
查看更多内容