Assignment problem

The problem of optimally assigning $ m $ individuals to $ m $ jobs. It can be formulated as a linear programming problem that is a special case of the transport problem:

maximize $ \sum _ c _ x _ $

$$ \sum _ < j >x _ = a _ , i = 1 \dots m $$

(origins or supply),

$$ \sum _ < i >x _ = b _ , j = 1 \dots n $$

(destinations or demand), where $ x _ \geq 0 $ and $ \sum a _ = \sum b _ $, which is called the balance condition. The assignment problem arises when $ m = n $ and all $ a _ $ and $ b _ $ are $ 1 $.

If all $ a _ $ and $ b _ $ in the transposed problem are integers, then there is an optimal solution for which all $ x _ $ are integers (Dantzig's theorem on integral solutions of the transport problem).

In the assignment problem, for such a solution $ x _ $ is either zero or one; $ x _ = 1 $ means that person $ i $ is assigned to job $ j $; the weight $ c _ $ is the utility of person $ i $ assigned to job $ j $.

The special structure of the transport problem and the assignment problem makes it possible to use algorithms that are more efficient than the simplex method. Some of these use the Hungarian method (see, e.g., [a5], [a1], Chapt. 7), which is based on the König–Egervary theorem (see König theorem), the method of potentials (see [a1], [a2]), the out-of-kilter algorithm (see, e.g., [a3]) or the transportation simplex method.

In turn, the transportation problem is a special case of the network optimization problem.

A totally different assignment problem is the pole assignment problem in control theory.

References

How to Cite This Entry:
Assignment problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Assignment_problem&oldid=45228

This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article