We describe a new paradigm for designing parallel algorithms that employs approximation techniques. Instead of solving a problem exactly, for which parallel algorithms might not exist, we seek a solution with provable approximation guarantees via approximation algorithms. Furthermore, we design approximation algorithms with high degrees of concurrency. We show matchings and edge covers in graphs as examples of this paradigm.
We describe 1/2-approximation algorithm for maximum weighted b-matching, and 3/2- and 2-approximation algorithms for minimum weighted b-edge covers. The ½-approximation algorithm for matchings may be viewed as the classical Gale-Shapley algorithm for stable matchings. We show that this technique leads to fast and scalable parallel algorithms for these problems on shared memory and distributed memory computers. We will also describe applications of matchings and edge covers to solve the k-nearest neighbor graph computations and adaptive anonymity problems.
Alex Pothen is a Professor of Computer Science at Purdue University. His research interests are in graph algorithms, parallel computing, scientific computing, and bioinformatics. He led the founding of the combinatorial scientific computing (CSC) community, which now holds biennial conferences on CSC organized through the Society for Industrial and Applied Mathematics. He has directed the CSCAPES Institute, a pioneering research center for the applications of graph algorithms to scientific computing, and is involved with the U.S. Exascale Computing Project of the Department of Energy. He is an editor of the Journal of the ACM and a former editor of SIAM Review.