Computer Science Department
School of Computer Science, Carnegie Mellon University
Efficient Parallel Approximation Algorithms
Over the past few decades, advances in approximation algorithms have enabled near-optimal solutions to many important, but computationally hard, problems to be found efficiently. But despite the resurgence of parallel computing in recent years, only a small number of these algorithms have been considered from the standpoint of parallel computation. Furthermore, among those for which parallel algorithms do exist, the algorithms – mostly developed in the late 80s and early 90s – follow a design principle that puts heavy emphasis on achieving polylogarithmic depth, with little regard to work, generally resulting in algorithms that perform substantially more work than their sequential counterparts. As a result, on a modest number of processors, these highly parallel–but "heavy"–algorithms are unlikely to perform competitively with the state-of-the-art sequential algorithms. îis motivates the question: How can one design a parallel approximation algorithm that obtains non-trivial speedups over its sequential counterpart, even on a modest number of processors?
In this thesis, we explore a set of key algorithmic techniques that facilitate the design, analysis, and implementation of a wide variety of efficient parallel approximation algorithms. This includes:
– Maximal nearly independent set. A natural generalization of
maximal independent set (MIS) solvable in linear work, which leads to
linear-work RNC ((1+ ε) ln n)-approximation set cover, (1-1/e-ε)-approximation (prefix optimal) max cover, and (4+ε)-approximation
min-sum set cover–and a work-efficient RNC (1:861+&episilon;)-approximation
for facility location.