A new multi-augmenting algorithm for the assignment problem

Abstract

We propose a new multi-augmenting algorithm for the assignment problem. It is motivated by the relation between the existing multi-augmenting algorithm [1] and a folklore method to find initial assignments. The folklore is named as the reduction method in the sense that it finds assignment by reducing the cost matrix. The reduction method consists of two steps, column reduction and row reduction. Nawijn and Dorhout [2] showed that the expected number of assignments by the full reduction approaches eighty-one percent of the maximum cardinality matching, whereas the expected number only by the column reduction is approximately sixty-three percent. The existing multi-augmenting algorithm repeatedly calls an algorithm for the shortest path problem to find augmenting paths, which can be regarded as the generalization of the column reduction. Therefore, we extend the multi-augmenting algorithm by adding a procedure corresponding to the generalized row reduction. The extended algorithm is based on a sequence of two shortest path sub-problems constructing an outward tree and an inward tree respectively. However, the second sub-problem is not expected to cost as much as the first one as the information of the outward tree accelerates the algorithm for the second one.