# Sinkhorn Algorithm for Lifted Assignment Problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2017.

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

- [A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2204.12805/) (2022)
- [Partial-to-Partial Shape Matching with Geometric Consistency](https://mlsanity.com/paper/2404.12209/) (2024)
- [Compositional Generalization without Trees using Multiset Tagging and Latent Permutations](https://mlsanity.com/paper/2305.16954/) (2023)
- [SIGMA: Scale-Invariant Global Sparse Shape Matching](https://mlsanity.com/paper/2308.08393/) (2023)
- [Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem](https://mlsanity.com/paper/2406.09899/) (2024)
- [Fast Globally Optimal and Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2504.06385/) (2025)
- [Deep Probabilistic Graph Matching](https://mlsanity.com/paper/2201.01603/) (2022)
- [An Integer Linear Programming Approach to Geometrically Consistent Partial-Partial Shape Matching](https://mlsanity.com/paper/2602.06590/) (2026)
- [Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe](https://mlsanity.com/paper/2609.25728/) (2026)

## Abstract (arXiv)

Recently, Sinkhorn's algorithm was applied for approximately solving linear programs emerging from optimal transport very efficiently. This was accomplished by formulating a regularized version of the linear program as Bregman projection problem onto the polytope of doubly-stochastic matrices, and then computing the projection using the efficient Sinkhorn algorithm, which is based on alternating closed-form Bregman projections on the larger polytopes of row-stochastic and column-stochastic matrices. In this paper we suggest a generalization of this algorithm for solving a well-known lifted linear program relaxations of the Quadratic Assignment Problem (QAP), which is known as the Johnson Adams (JA) Relaxation. First, an efficient algorithm for Bregman projection onto the JA polytope by alternating closed-form Bregman projections onto one-sided local polytopes is devised. The one-sided polytopes can be seen as a high-dimensional, generalized version of the row/column-stochastic polytopes. Second, a new method for solving the original linear programs using the Bregman projections onto the JA polytope is developed and shown to be more accurate and numerically stable than the standard approach of driving the regularizer to zero. The resulting algorithm is considerably more scalable than standard linear solvers and is able to solve significantly larger linear programs.