This repository contains code for optimizing combinatorial optimization problems by message passing techniques. The solvers work on the Lagrange decomposition of the specific optimization problem and monotonously improve the bound of the Lagrange dual function. A solution of the original primal problem is computed by rounding strategies.
Supported combinatorial optimization problems:
S. Haller, B. Savchynskyy.
“A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem”.
arXiv Pre-Print 2024. [PDF] [Website & Paper Specific Code]
S. Haller, L. Feineis, L. Hutschenreiter, F. Bernard, C. Rother, D. Kainmüller, P. Swoboda, B. Savchynskyy.
“A Comparative Study of Graph Matching Algorithms in Computer Vision”.
ECCV 2022 [PDF] [Website]
L. Hutschenreiter, S. Haller, L. Feineis, C. Rother, D. Kainmüller, B. Savchynskyy.
“Fusion Moves for Graph Matching”.
ICCV 2021. [PDF]
S. Haller, M. Prakash, L. Hutschenreiter, T. Pietzsch, C. Rother, F. Jug, P. Swoboda, B. Savchynskyy.
“A Primal-Dual Solver for Large-Scale Tracking-by-Assignment”.
AISTATS 2020. [pdf]
V. Kolmogorov.
“Convergent tree-reweighted message passing for energy minimization”.
PAMI 2006. [pdf]