Assignment problem: Difference between revisions

Revision as of 10:52, 25 October 2003

Revision as of 05:58, 12 November 2003

Line 5:

The cost of an assignment is determined from a ''cost function'', which gives the cost of assigning a particular agent to a particular task. The overall cost of the assignment is then equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing).

The assignment problem is a special case of another optimization problem known as the [[transportation problem]], which is a special case the [[maximal 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 problem has more efficient algorithms designed to take advantage of its special structure. It is knowknown that an algorithm exists to solve the assignment problem within time bounded by a polynomial expression of the number of agents.

The requirement about equal number of agents and tasks could be relaxed, as shown in the example below.