Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
Created page with "== Title == Parallel Algorithms for Geometric Graph Problems == Speaker == Krzysztof Onak, IBM TJ Watson Research Center == Abstract == Over the past decade a number of para..."
== Title ==
Parallel Algorithms for Geometric Graph Problems
== Speaker ==
Krzysztof Onak, IBM TJ Watson Research Center
== Abstract ==
Over the past decade a number of parallel systems such as MapReduce, Hadoop, and Dryad have become widely successful in practice. In this talk, I will present a new algorithmic framework for geometric graph problems for these kinds of systems. 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, 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 modern parallel systems. For example, it yields a new algorithm for approximating EMD in the plane in near-linear time. 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, which was raised as an open question in their work.
Joint work with Alexandr Andoni (Microsoft), Aleksandar Nikolov (Rutgers University), and Grigory Yaroslavtsev (Brown University).
Parallel Algorithms for Geometric Graph Problems
== Speaker ==
Krzysztof Onak, IBM TJ Watson Research Center
== Abstract ==
Over the past decade a number of parallel systems such as MapReduce, Hadoop, and Dryad have become widely successful in practice. In this talk, I will present a new algorithmic framework for geometric graph problems for these kinds of systems. 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, 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 modern parallel systems. For example, it yields a new algorithm for approximating EMD in the plane in near-linear time. 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, which was raised as an open question in their work.
Joint work with Alexandr Andoni (Microsoft), Aleksandar Nikolov (Rutgers University), and Grigory Yaroslavtsev (Brown University).
