Graphics enhanced version of this site

The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs
G.A. Mills-Tettey, A. Stentz, and M.B. Dias
tech. report CMU-RI-TR-07-27, Robotics Institute, Carnegie Mellon University, July, 2007.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [139 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

In this paper, we present the dynamic Hungarian algorithm, applicable to optimally solving the assignment problem in situations with changing edge costs or weights. This problem is relevant, for example, in a transportation domain where the unexpected closing of a road translates to changed transportation costs. When such cost changes occur after an initial assignment has been made, the new problem, like the original problem, may be solved from scratch using the well-known Hungarian algorithm. However, the dynamic version of the algorithm which we present solves the new problem more efficiently by repairing the initial solution obtained before the cost changes. We present proofs of the correctness and efficiency of our algorithm and present simulation results illustrating its efficiency.

Number of pages: 19

G.A. Mills-Tettey, A. Stentz, and M.B. Dias, The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs, tech. report CMU-RI-TR-07-27, Robotics Institute, Carnegie Mellon University, July, 2007.

@techreport{Mills-Tettey_2007_5805,
   author = "G. Ayorkor Mills-Tettey and Anthony (Tony) Stentz and M Bernardine Dias",
   title = "The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs",
   institution = "Robotics Institute, Carnegie Mellon University",
   month = "July",
   year = "2007",
   number = "CMU-RI-TR-07-27",
   address = "Pittsburgh, PA"
}