From Kantorovitch Problem to Linear Sum Assignment Problem

Romain Raveaux (1)

1 RFAI - Reconnaissance des formes et analyse d'images

The goal of this technical report is to detail the link between the Linear Sum Assignment Problem (LSAP) and the Kantorovitch Problem (KP) also called Optimal Transport. This relation is not new and is reported in \cite{peyre2020computational}

Keywords: Linear Sum Assignment; Kantorovitch; Optimal Transport; Matching

Domains: Image Processing [eess.IV]; Computer Vision and Pattern Recognition [cs.CV]

Romain Raveaux. From Kantorovitch Problem to Linear Sum Assignment Problem. [Intern report] Université de tours. 2021. ⟨hal-03388191v2⟩