A common parallel framework for LLP combinatorial problems
2026-03-13 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors created a general tool called LLP-FW to solve many different optimization problems without needing special custom code for each. Instead of writing unique solutions for things like shortest paths or job scheduling, LLP-FW uses a common approach to handle them all by working on parts of the problem in parallel until it finds an answer. The only thing users need to provide is how to identify bad states and how to fix them. The authors tested LLP-FW on several problems and found it works similarly or better than custom solutions.
lock-free algorithmscombinatorial optimizationLattice-Linear Predicateparallel computingforbidden local statesSingle Source Shortest PathsStable Marriagejob schedulingBreadth-First Searchparallel reduction
Authors
David Ribeiro Alves, Vijay K. Garg
Abstract
Traditional lock-free parallel algorithms for combinatorial optimization problems, such as shortest paths, stable matching, and job scheduling require programmers to write problem-specific routines and synchronization code. We propose a general-purpose lock-free runtime, LLP-FW that can solve all combinatorial optimization problems that can be formulated as a Lattice-Linear Predicate by advancing all forbidden local states in parallel until a solution emerges. The only problem-specific code is a definition of the forbiddenness check and a definition of the advancement. We show that LLP-FW can solve several different combinatorial optimization problems, such as Single Source Shortest Paths (SSSP), Breadth-First Search (BFS), Stable Marriage, Job Scheduling, Transitive Closure, Parallel Reduction, and 0-1 Knapsack. We compare LLP-FW against hand-tuned, custom solutions for these seven problems and show that it compares favorably in the majority of cases.