A rough draft of the book is available here. pdf




In this forthcoming book, I show that many algorithms can be derived in a systematic manner. A companion book shows that many parallel algorithms can also be derived using this approach. In our approach, a problems is cast as searching for an element satisfying an appropriate predicate in a distributive lattice. Our method solves and generalizes many classical combinatorial optimization problems including:

• Shortest Path Problems : Dijkstra's algorithm, Bellman-Ford's algorithm, Johnson's algorithm
• Stable Marriage Problem : Gale-Shapley algorithm, Irving's algorithms for Super-Stable marriage and Strongly-Stable Marriage
• Assignment Problem : Demange-Gale-Sotomayor algorithm
• Housing Allocation : Gale's algorithm
• Dynamic Programming Problems : Algorithm for the longest subsequence, Optimal binary search tree problem, Knapsack problem
• Minimum Spanning Tree Problem : Prim's extended algorithm
• Horn Satisfiability Problem : Algorithm to check for satisfiability of Horn's formula
• Connected Components Problem : Algorithm to determine connected components in an undirected graph

• Vijay K. Garg, Predicate Detection to Solve Combinatorial Optimization Problems SPAA 2020 pdf ... slides ... video
• Vijay K. Garg, A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems ICDCN'22, arxiv-version
• Vijay K. Garg, Invited Paper: A Lattice Linear Predicate Parallel Algorithm for the Housing Market Problem Proc. SSS 2021. pdf
• Arya Tanmay Gupta, Sandeep S Kulkarni, Extending Lattice linearity for Self-Stabilizing Algorithms Proc. SSS 2021. arxiv-version
• David R. Alves, Vijay K. Garg, Parallel Minimum Spanning Tree Algorithms via Lattice Linear Predicate Detection Proc. PDCO (Parallel and Distributed Combinatorics and Optimization) 2022. pdf
• Vijay K. Garg, Lattice Linear Predicate Algorithms for the Constrained Stable Marriage Problem with Ties arxiv-version