# A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2016.

## Built on by (most cited first, 7 of 7)

- [Making Higher Order MOT Scalable: An Efficient Approximate Solver for Lifted Disjoint Paths](https://mlsanity.com/paper/2108.10606/) (2021)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [R-U-SURE? Uncertainty-Aware Code Suggestions By Maximizing Utility Across Random User Intents](https://mlsanity.com/paper/2303.00732/) (2023)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [Efficient Linear Attention for Fast and Accurate Keypoint Matching](https://mlsanity.com/paper/2204.07731/) (2022)
- [One-shot Key Information Extraction from Document with Deep Partial Graph Matching](https://mlsanity.com/paper/2109.13967/) (2021)
- [Convergence of Some Convex Message Passing Algorithms to a Fixed Point](https://mlsanity.com/paper/2403.07004/) (2024)

## Abstract (arXiv)

We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In his work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.