# Relative-Interior Solution for the (Incomplete) Linear Assignment Problem with Applications to the Quadratic Assignment Problem

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 52 references that are in the map.
- First posted on arXiv 26 Jan 2023.

## Builds on (most cited first, 6 of 6)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [A Comparative Study of Graph Matching Algorithms in Computer Vision](https://mlsanity.com/paper/2207.00291/) (2022)
- [MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models](https://mlsanity.com/paper/2004.08227/) (2020)
- [Discrete graphical models -- an optimization perspective](https://mlsanity.com/paper/2001.09017/) (2020)
- [Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming: Part I](https://mlsanity.com/paper/2211.00876/) (2022)

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

- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)

## Abstract (arXiv)

We study the set of optimal solutions of the dual linear programming formulation of the linear assignment problem (LAP) to propose a method for computing a solution from the relative interior of this set. Assuming that an arbitrary dual-optimal solution and an optimal assignment are available (for which many efficient algorithms already exist), our method computes a relative-interior solution in linear time. Since the LAP occurs as a subproblem in the linear programming (LP) relaxation of the quadratic assignment problem (QAP), we employ our method as a new component in the family of dual-ascent algorithms that provide bounds on the optimal value of the QAP. To make our results applicable to the incomplete QAP, which is of interest in practical use-cases, we also provide a linear-time reduction from the incomplete LAP to the complete LAP along with a mapping that preserves optimality and membership in the relative interior. Our experiments on publicly available benchmarks indicate that our approach with relative-interior solution can frequently provide bounds near the optimum of the LP relaxation and its runtime is much lower when compared to a commercial LP solver.