We describe a paradigm for designing parallel algorithms via approximation, and illustrate it on the bedgecover problem. A bedgecover of minimum weight in a graph is a subset $C$ of its edges such that at least a specified number $b(v)$ of edges in $C$ is incident on each vertex $v$, and the sum of the edge weights in $C$ is minimum. The Greedy algorithm and a variant, the LSE algorithm, provide $3/2$approximation guarantees in the worstcase for this problem, but these algorithms have limited parallelism. Hence we design two new $2$approximation algorithms with greater concurrency. The MCE algorithm reduces the computation of a bedgecover to that of finding a b'matching, by exploiting the relationship between these subgraphs in an approximation context. The LSENW is derived from the LSEalgorithm using static edge weights rather than dynamically computing effective edge weights. This relaxation gives LSE a worse approximation guarantee but makes it more amenable to parallelization. We prove that both the MCE and LSENW algorithms compute the same bedgecover with at most twice the weight of the minimum weight edge cover. In practice, the $2$approximation and $3/2$approximation algorithms compute edge covers of weight within $10\%$ the optimal. We implement three of themore »
A new 3/2approximation algorithm for the bedge cover problem
We describe a 3/2approximation algorithm, \lse, for computing a bedgecover
of minimum weight in a graph with weights on the edges.
The bedgecover problem is a generalization of the betterknown 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 bedgecover 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 bedge 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 bedge 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 more »
 Award ID(s):
 1637534
 Publication Date:
 NSFPAR ID:
 10039355
 Journal Name:
 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing
 Page Range or eLocationID:
 5261
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the maximum vertexweighted matching problem (MVM), in which nonnegative weights are assigned to the vertices of a graph, and the weight of a matching is the sum of the weights of the matched vertices. Although exact algorithms for MVM are faster than exact algorithms for the maximum edgeweighted matching problem, there are graphs on which these exact algorithms could take hundreds of hours. For a natural number k, we design a k/(k + 1)approximation algorithm for MVM on nonbipartite graphs that updates the matching along certain short paths in the graph: either augmenting paths of length at most 2k + 1 or weightincreasing paths of length at most 2k. The choice of k = 2 leads to a 2/3approximation algorithm that computes nearly optimal weights fast. This algorithm could be initialized with a 2/3approximate maximum cardinality matching to reduce its runtime in practice. A 1/2approximation algorithm may be obtained using k = 1, which is faster than the 2/3approximation algorithm but it computes lower weights. The 2/3approximation algorithm has time complexity O(Δ2m) while the time complexity of the 1/2approximation algorithm is O(Δm), where m is the number of edges and Δ is the maximum degree of a vertex.more »

We describe two new 3/2approximation algorithms and a new 2approximation algorithm for the minimum weight edge cover problem in graphs. We show that one of the 3/2approximation algorithms, the Dual cover algorithm, computes the lowest weight edge cover relative to previously known algorithms as well as the new algorithms reported here. The Dual cover algorithm can also be implemented to be faster than the other 3/2approximation algorithms on serial computers. Many of these algorithms can be extended to solve the 6Edge cover problem as well. We show the relation of these algorithms to the KNearest Neighbor graph construction in semisupervised learning and other applications.

Bender, M. ; Gilbert, J. ; Hendrickson, B. ; Sullivan, B. (Ed.)We design new serial and parallel approximation algorithms for computing a maximum weight bmatching in an edgeweighted graph with a submodular objective function. This problem is NPhard; the new algorithms have approximation ratio 1/3, and are relaxations of the Greedy algorithm that rely only on local information in the graph, making them parallelizable. We have designed and implemented Local Lazy Greedy algorithms for both serial and parallel computers. We have applied the approximate submodular bmatching algorithm to assign tasks to processors in the computation of Fock matrices in quantum chemistry on parallel computers. The assignment seeks to reduce the run time by balancing the computational load on the processors and bounding the number of messages that each processor sends. We show that the new assignment of tasks to processors provides a four fold speedup over the currently used assignment in the NWChemEx software on 8000 processors on the Summit supercomputer at Oak Ridge National Lab.

We study the multilevel Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of nonproportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln T  + 1), lρ}approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and l is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ ≈ 1.39, for example). In this paper, we describe a natural generalization to the multilevel case of the classical (singlelevel) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. Wemore »