preprint · arXiv (Cornell University) · 2022

A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems

Cited by 3Open access

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 works correctly in a distributed system setting where a processor may use an older value of a variable stored at a different processor.

Cite this paper

APA 7

Garg, V. K. (2022). A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems. arXiv (Cornell University), 72–76. https://doi.org/10.1145/3491003.3491019

MLA 9

Garg, Vijay K. “A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems.” arXiv (Cornell University), 2022, pp. 72–76, https://doi.org/10.1145/3491003.3491019.

Chicago

Garg, Vijay K. 2022. “A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems.” arXiv (Cornell University): 72–76. https://doi.org/10.1145/3491003.3491019.

Harvard

Garg, V.K. (2022) ‘A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems’, arXiv (Cornell University), pp. 72–76. Available at: https://doi.org/10.1145/3491003.3491019.

BibTeX

@misc{garg2022lattice,
  title = {{A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems}},
  author = {Garg, Vijay K.},
  journal = {arXiv (Cornell University)},
  pages = {72--76},
  year = {2022},
  doi = {10.1145/3491003.3491019}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.