Assignment problem: Difference between revisions

Revision as of 05:30, 14 August 2003

Revision as of 14:20, 28 September 2003

Line 1:

An '''assignment problem''' is anya mathematicaltype optimizationof problem whosein solution[[mathematics]] consistswhere of assigningthe members of one set, say(referred assignees,to as ''agents'') must be assigned to the members of another set, say(referred tasks.to Providedas each''tasks'') setin issuch ofa equalway size andthat each elementagent is assigned to exactly one element from the other set. Associated withtask, each possible pairing (assignee, task) ishas aexactly cost.one Theagent optimalassigned assignmentto willit, optimizeand the sumtotal ''cost'' of the assignment costsis minimized.

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).

For example, suppose that a taxi firm has three taxis available, and three customers wishing to be picked up at the same time. Then for each taxi, the cost of picking up a particular customer will depend on how far the taxi must drive to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total driving.

The assignment problem is a special case of another optimization problem known as the '''transportation problem''', which in turn is a special case of a problem known as '''maximal flow problem''', which in turn is a special case of a [[linear program]]. While it is possible to solve all these problems with the '''simplex algorithm''', each of these problems has more efficient algorithms designed to take advantage of their special structure. It is know that an algorithm exists to solve the assignment problem within time bounded by a polynomial expression of the number of assignees.