The Dynamic Hungarian Algorithm for the Assignment Problem

The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs G. Ayorkor Mills-Tettey Anthony Stentz M. Bernardine Dias CMU-RI-TR-07-27 July 2007 Robotics Institute Carnegie Mellon University Pittsburgh, Pennsylvania 15213 c Carnegie Mellon University 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. I Contents 1 Introduction 1 2 Background 2 2.1 Terminology and Notation . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Hungarian Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3.1 The incremental assignment problem. . . . . . . . . . . . . . 5 2.3.2 The dynamic assignment problem. . . . . . . . . . . . . . . . 5 3 The Assignment Problem with Changing Costs 6 4 Example 8 5 Proofs 10 6 Numerical Results 12 7 Conclusions 13 III 1 Introduction The assignment problem, also known as the maximum weighted bipartite matching problem, is a widely-studied problem applicable to many domains [2]. It can be stated as follows: given a set of workers, a set of jobs, and a set of ratings indicating how well each worker can perform each job, determine the best possible assignment of workers to jobs, such that the total rating is maximized [5]. More generally, given a bipartite graph made up of two partitions V and U, and a set of weighted edges E between the two partitions, the problem requires the selection of a subset of the edges with a maximum sum of weights such that each node vi 2 V or ui 2 U is connected to at most one edge [6]. The problem may also be phrased as a minimization problem by considering, instead of edge weights wij, a set of non-negative edge costs, cij = W ¡wij, where W is at least...

Website: www.ri.cmu.edu | Filesize: -
No of Page(s): 19
Download The Dynamic Hungarian Algorithm for the Assignment Problem with ....pdf