# A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems

Source: [A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems](<https://www.sota2.com/research/paper/68fa697f1e209131cea22742>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T23:01:46.798Z

Authors: Vijay K. Garg

Published: 2021-03-10T18:54:04.000Z

## Abstract

It has been shown that the parallel Lattice Linear Predicate (LLP) algorithm solves many combinatorial optimization problems such as the shortest path problem, the stable marriage problem and the market clearing price problem. In this paper, we give the parallel LLP algorithm for many dynamic programming problems. In particular, we show that the LLP algorithm solves the longest subsequence problem, the optimal binary search tree problem, and the knapsack problem. Furthermore, the algorithm can be used to solve the constrained versions of these problems so long as the constraints are lattice linear. The parallel LLP algorithm requires only read-write atomicity and no higher-level atomic instructions.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2103.06264>)

[PDF](<https://arxiv.org/pdf/2103.06264.pdf>)
