A new multi-augmenting algorithm for the assignment problem

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 588
  • Download : 295
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.
Publisher
Veszprem Optimization Conference: Advanced Algorithms
Issue Date
2006-12
Keywords

Assignment Problem

Citation

VOCAL 2006, December 13-15, 2006, Veszprem, Hungary

URI
http://hdl.handle.net/10203/7666
Appears in Collection
IE-Conference Papers(학술회의논문)
Files in This Item
AP_Vesprem.pdf(8.4 kB)Download

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0