%AKhan, Arif%APothen, Alex%D2016%I
%K
%MOSTI ID: 10039355
%PMedium: X
%TA new 3/2-approximation algorithm for the b-edge cover problem
%XWe describe a 3/2-approximation algorithm, \lse, for computing a b-edgecover
of minimum weight in a graph with weights on the edges.
The b-edgecover 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-edgecover problem, we minimize the sum of the weights of the edges in C.
We prove that the Locally Subdominant edge (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 algorithm is 3 to 5 times 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.
Country unknown/Code not availablehttps://doi.org/10.1137/1.9781611974690.ch6OSTI-MSA