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.