# Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

arXiv: https://arxiv.org/abs/2605.09382 · HTML: https://mlsanity.com/paper/2605.09382/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 29 references that are in the map.
- First posted on arXiv 10 May 2026.

## Builds on (most cited first, 15 of 15)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems](https://mlsanity.com/paper/2310.10603/) (2023)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Large Scale Real-World Multi-Person Tracking](https://mlsanity.com/paper/2211.02175/) (2022)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Approximation Algorithms for Combinatorial Optimization with Predictions](https://mlsanity.com/paper/2411.16600/) (2024)
- [GLAN: A Graph-based Linear Assignment Network](https://mlsanity.com/paper/2201.02057/) (2022)
- [SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching](https://mlsanity.com/paper/2205.13679/) (2022)
- [Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimization](https://mlsanity.com/paper/2302.00928/) (2023)
- [New Auction Algorithms for the Assignment Problem and Extensions](https://mlsanity.com/paper/2310.03159/) (2023)

## Abstract (arXiv)

The Linear Assignment Problem is a fundamental combinatorial optimization task where classical exact solvers ensure optimality but suffer from an O(N3) bottleneck, while recent neural approximations struggle with scalability and exactness. We propose a learning-augmented framework that accelerates exact solvers by predicting dual variables to warm-start the search, backed by a fallback mechanism to preserve worst-case guarantees. Central to our approach is RowDualNet, a lightweight, row-independent architecture that avoids the O(N2) memory bottleneck of graph models, enabling scalable neural warm-starting up to N=16,384. Feasibility is guaranteed by construction via the Min-Trick mechanism, completely eliminating the need for costly iterative projections. Empirically, our method drastically reduces the search effort of the Jonker-Volgenant (LAPJV) algorithm, yielding robust zero-shot generalization with strict optimality and end-to-end speedups of over 2x on complex synthetic data, 1.25x on real-world tracking, and 1.5x on transportation networks.