Journal
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING
Volume -, Issue -, Pages 798-811Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3055399.3055460
Keywords
Massively parallel computing; Dynamic programming
Categories
Funding
- NSF [CCF-1409130, CCF-1617653, CCF-1617724]
- Google Research Award
- Yahoo Research Award
- Direct For Computer & Info Scie & Enginr [1409130] Funding Source: National Science Foundation
- Division of Computing and Communication Foundations [1409130] Funding Source: National Science Foundation
Ask authors/readers for more resources
Modern science and engineering is driven by massively large data sets and its advance heavily relies on massively parallel computing platforms such as Spark, MapReduce, and Hadoop. Theoretical models have been proposed to understand the power and limitations of such platforms. Recent study of developed theoretical models has led to the discovery of new algorithms that are fast and efficient in both theory and practice, thereby beginning to unlock their underlying power. Given recent promising results, the area has turned its focus on discovering widely applicable algorithmic techniques for solving problems efficiently. In this paper we make progress towards this goal by giving principles for simulating a large class of sequential dynamic programs in the distributed setting. In particular, we identify two key properties, monotonicity and decomposibility, which allow us to derive efficient distributed algorithms for problems possessing the properties. We showcase our framework by considering several core dynamic programming applications, Longest Increasing Subsequence, Optimal Binary Search Tree, and Weighted Interval Selection. For these problems, we derive algorithms yielding solutions that are arbitrarily close to the optimum, using O(1) rounds and (O) over tilde (n/m) memory on each machine where n is the input size and m is the number of machines available.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available