## Aperçu

**LSAPE**is a set of C++ functions for solving the Linear Sum Assignment Problem with Edition,

*i.e.*error-tolerant weighted bipartite matching between two sets U and V. The problem consists in transforming U into V by means of edit operations:

- each element of U is substituted by a unique element of V, or removed, and
- each element of V, that has not been used for a substitution, is inserted into U.

The removal of an element from a set is equivalent to its insertion in the other set. Each possible edit operation (substitution, removal or insertion) is penalized by a real non-negative cost. The cost of a transformation is then measured by summing the costs of its edit operations. A solution to the problem is defined as a transformation having a minimal cost, among all transformations from U to V.

This problem is for instance used to approximate the graph edit distance, see Approximate graph edit distance computation by means of bipartite graph matching by *K. Riesen* and *H. Bunke* (Image and Vision Computing 27, 2009).

The LSAPE is a binary linear programming problem. It can be solved in polynomial time complexity. The primal-dual Hungarian algorithm implemented in **LSAPE** solves the LSAPE in O(n^2m+nm^2) time complexity and O(nm) memory space, where n is the size of U and m the one of V. See Linear sum assignment problem with edition by *S. Bougleux* and *L. Brun* (Technical Report, GREYC, October 2015) for more details.

This algorithm adapts to edit operations the well-known O(n^3) primal-dual version of the Hungarian algorithm proposed by *E.L. Lawler* in *Combinatorial Optimization: Networks and Matroids* (Holt, Rinehart and Wilson, New York, 1975). See also the book *Assignment Problems* by *R. Burkard*, *M. Dell’Amico*, and *S. Martello* (SIAM, 2009) for a complete description.

**LSPAE** is distributed under LGPL. Matlab interface, comparisons with the squared-LSAPE and examples are provided.

### Membres

Manager: Benoit Gauzere, Luc Brun, Sebastien Bougleux

Développeur: Evariste Daller, Luc Brun, Sebastien Bougleux