Abstract
I will present two examples of how parallelization is aided by approximating the process. The first story is about approximating a greedy process. Greedy set cover is a simple algorithm that gives the best known approximation under standard complexity assumptions. But from a parallelization point of view, it doesn't parallelize readily because each greedy step depends on the choices made in previous steps. We will look at how a simple approximation breaks this dependency without substantially harming the solution's quality.
The second story is about approximating triangle count using streaming algorithms techniques. The number of triangles in a graph is an important metric with a wide variety of applications. We will see how to design a streaming algorithm to approximate the count, and using ideas from the streaming algorithm, we will derive an efficient parallel algorithm which processes edges in the streaming graph in bulk. When the graph has sufficiently many triangles, the total work is nearly linear.