@InProceedings{CI-Brun2022,


author = {Luc Brun and Benoit Gauzere and Guillaume Renton and Sebastien Bougleux and Florian Yger},
title = {A differentiable approximation for the Linear Sum Assignment Problem with Edition (LSAPE)},
booktitle = {Proceedinds of 26th ICPR 2022},
year = 2022,
month = {August},
address = {Montréal},
organization = {IAPR},
publisher = {IEEE},
theme="pattern",
url={HAL:=https://hal.archives-ouvertes.fr/hal-03768664, TR(pdf):=https://hal.archives-ouvertes.fr/hal-03454896/file/main.pdf}
abstract="Linear Sum Assignment Problem (LSAP) consists in
mapping two sets of points of equal sizes according to a matrix
encoding the cost of mapping each pair of points. The Linear
Sum Assignment Problem with Edition (LSAPE) extends this
problem by allowing the mapping of sets of different sizes and
adding the possibility to reject some matchings. This problem
is set up by a rectangular cost matrix whose last column and
last line encode the costs of rejecting the match of an element
of respectively the first and the second sets. LSAPE has been
the workhorse of many fundamental graph problems such as
graph edit distance, median graph computation or sub graph
matching. LSAP may be solved using the Hungarian algorithm
while an equivalent efficient discrete algorithm has been designed
for LSAPE. However, while the Sinkhorn algorithm constitutes
a continuous solver for LSAP, no such algorithm yet exists for
LSAPE. This lack of solvers forbids the integration of LSAPE in
Neural networks requiring continuous operations from the input
to the final loss. This paper aims at providing such a solver,
hence paving the way to an integration of LSAPE solvers in
Neural Networks."

 }