Loading...
Please wait, while we are loading the content...
Similar Documents
The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs (2007)
| Content Provider | CiteSeerX |
|---|---|
| Author | Mills-Tettey, G. Ayorkor Stentz, Anthony Dias, M. Bernardine |
| Abstract | 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. |
| File Format | |
| Publisher Date | 2007-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dynamic Hungarian Algorithm Assignment Problem Changing Cost Cost Change New Problem Dynamic Version Original Problem Initial Assignment Present Proof Edge Cost Well-known Hungarian Algorithm Initial Solution Unexpected Closing Present Simulation Result Transportation Cost Transportation Domain |
| Content Type | Text |
