We describe a new paradigm for designing algorithms for computationally intensive problems. Instead of solving a problem exactly, for which parallel algorithms might not exist, we seek algorithms with provable approximation guarantees. Furthermore, we design approximation algorithms with high degrees of concurrency that achieve high performance on parallel computers. We show b-matchings and b-edge covers in graphs as examples of this paradigm.
We describe a 1/2-approximation algorithm for maximum weighted b-matching, and several 3/2- and 2-approximation algorithms for minimum weighted b-edge covers. The ½-approximation algorithm for matchings is related to 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 scaling to hundreds of thousands of cores. We will also describe applications of matchings and edge covers to solve a data privacy problem and the well-known k-nearest neighbor graph construction in semi-supervised learning.
Copyright. All Rights Reserved.