Assignment problem: Difference between revisions

Revision as of 23:39, 5 February 2004

Revision as of 02:21, 6 February 2004

Line 7:

If the numers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called ''Linear assignment problem''. Commonly, when spoken of ''Assignment problem'' without any additional qualification, then the ''Linear assignment problem'' is meant.

Another kinds are the [[Quadraticquadratic assignment problem]], [[Minmaxminmax assignment problem]].

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. Algorithm are known that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents.