A new multi-augmenting algorithm for the assignment problem

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 645
  • Download : 309
DC FieldValueLanguage
dc.contributor.authorChung, Eesuk-
dc.contributor.authorKang, Jayoung-
dc.contributor.authorPark, Sungsoo-
dc.identifier.citationVOCAL 2006, December 13-15, 2006, Veszprem, Hungaryen
dc.description.abstractWe 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.en
dc.publisherVeszprem Optimization Conference: Advanced Algorithmsen
dc.subjectAssignment Problemen
dc.titleA new multi-augmenting algorithm for the assignment problemen


  • mendeley


rss_1.0 rss_2.0 atom_1.0