Sinkhorn Algorithm for Lifted Assignment Problems

DOI10.1137/18m1196480zbMath1524.90270arXiv1707.07285OpenAlexW2963284675WikidataQ128080173 ScholiaQ128080173MaRDI QIDQ6133998

Yaron Lipman, Unnamed Author, Unnamed Author, Nadav Dym

Publication date: 25 July 2023

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.07285

zbMATH Keywords

convex relaxationsquadratic assignmentshape matchingSherali-AdamsJohnson-AdamsSinkhorn

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (2)

Unnamed Item ⋮ Transfer operators from optimal transport plans for coherent set detection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey for the quadratic assignment problem
• Bounds for the quadratic assignment problem using the bundle method
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• On the quadratic assignment problem
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• Proximal minimization algorithm with \(D\)-functions
• The invisible hand algorithm: solving the assignment problem with statistical physics
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• A dual framework for lower bounds of the quadratic assignment problem based on linearization
• A revised reformulation-linearization technique for the quadratic assignment problem
• A generalized solution of the orthogonal Procrustes problem
• Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
• The Quadratic Assignment Problem
• A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• P-Complete Approximation Problems
• Iterative Bregman Projections for Regularized Transportation Problems
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A new bound for the quadratic assignment problem based on convex quadratic programming

This page was built for publication: Sinkhorn Algorithm for Lifted Assignment Problems