Krzysztof Onak (IBM TJ Watson Research): Parallel Algorithms for Geometric Graph Problems
We give algorithms for geometric graph problems in modern parallel models such as MapReduce. Our algorithms produce approximate solutions for problems such as Minimum Spanning Tree (MST) and Earth-Mover Distance (EMD). Provided the underlying set of points lies in a space of constant dimension, only a constant number of rounds is necessary for producing a solution, while the total amount of space and communication remains linear in the size of the data. In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem, despite drawing significant attention in recent years.
Our algorithmic framework has implications beyond the MapReduce model. For example, it yields a new algorithm for approximating EMD in the plane in near-linear time n^(1+o(1)). We note that while recently Sharathkumar and Agarwal (STOC 2012) have developed a near-linear time algorithm for (1+epsilon)-approximating EMD, our approach is fundamentally different and also solves the transportation (cost) problem, raised as an open question in their work.
Joint work with Alexandr Andoni (Microsoft Research), Aleksandar Nikolov (Rutgers University), and Grigory Yaroslavtsev (Brown University).