A New 3/2-Approximation Algorithm for the b-Edge Cover Problem
A New 3/2-Approximation Algorithm for the b-Edge Cover Problem
复制标题
DOI：
10.1137/1.9781611974690.ch6
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Arif M. Khan;A. Pothen
中科院分区：
文献类型：
--
作者：
Arif M. Khan;A. Pothen
我们描述了一种 3/2 近似算法 LSE，用于计算边缘权重的图中最小权重的 b 边覆盖。 b-边覆盖问题是图中更为人所知的边覆盖问题的推广，其中的目标是选择图中边的子集 C，使得 C 中至少指定数量 b(v) 的边入射到每个顶点 v。在加权 b-边覆盖问题中，我们最小化 C 中边的权重之和。我们证明 LSE 算法计算的 b-边覆盖与该问题的贪心算法获得的 b-边覆盖相同。然而，贪心算法要求边按其有效权重排序，并且这些权重需要在每次迭代后更新。这些要求使得贪心算法对于大规模图来说是连续的并且不切实际。 LSE 算法避免了排序步骤，并且适合并行化。我们在串行机器上实现该算法，并将其性能与 b-Edge Cover 问题的一组近似算法进行比较。我们的结果表明，在串行处理器上，LSE 算法比贪婪算法快 3 到 5 倍。对于我们可以计算后者的问题，LSE 算法获得的近似边缘覆盖的权重最多比最佳权重大 17%。我们还研究了 b-Edge Cover 和 b-Matching 问题之间的关系，表明后者具有更快的实现速度，因为该算法中的边权重是静态的，并从后者获得了前者的启发式解决方案。
We describe a 3/2-approximation algorithm, LSE, for computing a b-Edge Cover of minimum weight in a graph with weights on the edges. The b-Edge Cover problem is a generalization of the better-known Edge Cover problem in graphs, where the objective is to choose a subset C of edges in the graph such that at least a specified number b(v) of edges in C are incident on each vertex v. In the weighted b-Edge Cover problem, we minimize the sum of the weights of the edges in C. We prove that the LSE algorithm computes the same b-Edge Cover as the one obtained by the Greedy algorithm for the problem. However, the Greedy algorithm requires edges to be sorted by their effective weights, and these weights need to be updated after each iteration. These requirements make the Greedy algorithm sequential and impractical for massive graphs. The LSE algorithm avoids the sorting step, and is amenable for parallelization. We implement the algorithm on a serial machine and compare its performance against a collection of approximation algorithms for the b-Edge Cover problem. Our results show that the LSE algorithm is 3× to 5× faster than the Greedy algorithm on a serial processor. The approximate edge covers obtained by the LSE algorithm have weights greater by at most 17% of the optimal weight for problems where we could compute the latter. We also investigate the relationship between the b-Edge Cover and the b-Matching problems, show that the latter has a faster implementation since edge weights are static in this algorithm, and obtain a heuristic solution for the former from the latter.