Content deleted Content added
→Unbalanced assignment: Fix phrasing: Matchings have fixed cardinalities |
|||
Line 32:
A naive solution for the assignment problem is to check all the assignments and calculate the cost of each one. This may be very inefficient since, with ''n'' agents and ''n'' tasks, there are ''n''! ([[factorial]] of ''n'') different assignments. Fortunately, there are many algorithms for solving the problem in time [[polynomial time|polynomial]] in ''n''.
The assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], each specialization has a small solution space and thus more efficient algorithms designed to take advantage of its special structure.
=== Balanced assignment ===
| |||