Assignment problem: Difference between revisions

Revision as of 02:21, 6 February 2004

Revision as of 02:23, 6 February 2004

Line 5:

:There are a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any task, incurring some ''cost'' that may vary depending on the assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the ''total cost'' of the assignment is minimized.

If the numersnumbers 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 [[quadratic assignment problem]], [[minmax assignment problem]].