Parallel Algorithms for Geometric Graph Problems

被引:90
作者
Andoni, Alexandr [1 ]
Nikolov, Aleksandar [2 ]
Onak, Krzysztof [3 ]
Yaroslavtsev, Grigory [4 ]
机构
[1] Microsoft Res, Redmond, WA 98052 USA
[2] Rutgers State Univ, New Brunswick, NJ USA
[3] IBM Res, Yorktown Hts, NY USA
[4] Brown Univ, ICERM, Providence, RI 02912 USA
来源
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2014年
关键词
parallel computation; minimum spanning tree; earth-mover distance; MapReduce;
D O I
10.1145/2591796.2591805
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a (1 + epsilon)-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem [9], despite drawing significant attention in recent years. We develop a general algorithmic framework that, besides MST, also applies to Earth-Mover Distance (EMD) and the transportation cost problem. Our algorithmic framework has implications beyond the MapReduce model. For example it yields a new algorithm for computing EMD cost in the plane in near-linear time, n(1+o epsilon(1)). We note that while recently [33] have developed a near-linear time algorithm for (1 + epsilon)-approximating EMD, our algorithm is fundamentally different, and, for example, also solves the transportation (cost) problem, raised as an open question in [33]. Furthermore, our algorithm immediately gives a (1+epsilon)-approximation algorithm with n(delta) space in the streaming with-sorting model with 1/delta(O(1)) passes. As such, it is tempting to conjecture that the parallel models may also constitute a concrete playground in the quest for efficient algorithms for EMD (and other similar problems) in the vanilla streaming model, a well-known open problem.
引用
收藏
页码:574 / 583
页数:10
相关论文
共 40 条