Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed, Nir Weinberger, Jose Yallouz
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| warm-start LAPJV with predicted duals | LAPJV · Dense Model, N=16,384 | end-to-end speedup: ≈2.0× vs SciPy, ≈2.5× vs LAP | Improved |
| warm-start LAPJV with predicted duals | LAPJV · Block-Structured Model, N=16,384 | end-to-end speedup: ≈2.25× vs SciPy, ≈4.0× vs LAP | Improved |
| warm-start at small size | LAPJV · N=512 | end-to-end speedup | Hurt |
| use neural warm-start on sparse MOT matrices | LAPJV · Multi-object tracking | end-to-end speedup: ≈1.25× vs LAP, ≈2× vs SciPy | Mixed |
| neural warm-start improves greedy matching | LAPJV · Dense/Block | greedy match rate: ≈26% -> ≈76% | Improved |
| add neural warm-start to reduce runtime variance | LAPJV · MOT | coefficient of variation: ≈45% -> ≈30% | Improved |
| replace RowDualNet with linear regression (ablation) | RowDualNet · Dense/Block | speedup: below baseline for N > 4,096 | Hurt |
| replace RowDualNet with Random or Row Mean heuristic (ablation) | RowDualNet · Dense | speedup: speedup <1.0 | Hurt |
| replace RowDualNet with time-bounded subgradient ascent (ablation) | RowDualNet · Dense/Block N=8192 | speedup: ≈2.5× -> ≈1.5× | Hurt |
| subgradient initialization on sparse MOT (ablation) | LAPJV · MOT | speedup: speedup < 1.0× | Hurt |
| add positional encodings to features (d=13 -> d=21) (ablation) | RowDualNet · Block-structured, N=4096 | speedup | Improved |
| add positional encodings to features (ablation) | RowDualNet · Dense, N=4096 | speedup | No clear effect |
Closest papers by meaning
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.86)
- AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs (NeurIPS 2026 · similarity 0.86)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.86)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.86)
- GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent (NeurIPS 2024 · similarity 0.85)
- Regularized Large Neighborhood Search (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
