English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Dynamic programming is a powerful technique that is, unfortunately, ofteninherently sequential. That is, there exists no unified method to parallelizealgorithms that use dynamic programming. In this paper, we attempt to addressthis issue in the Massively Parallel Computations (MPC) model which is apopular abstraction of MapReduce-like paradigms. Our main result is analgorithmic framework to adapt a large family of dynamic programs defined overtrees.  We introduce two classes of graph problems that admit dynamic programmingsolutions on trees. We refer to them as "(polylog)-expressible" and"linear-expressible" problems. We show that both classes can be parallelized in$O(\log n)$ rounds using a sublinear number of machines and a sublinear memoryper machine. To achieve this result, we introduce a series of techniques thatcan be plugged together. To illustrate the generality of our framework, weimplement in $O(\log n)$ rounds of MPC, the dynamic programming solution ofgraph problems such as minimum bisection, $k$-spanning tree, maximumindependent set, longest path, etc., when the input graph is a tree.

Massively Parallel Dynamic Programming on Trees