Assignment problem: Difference between revisions

Revision as of 09:46, 25 October 2021

Revision as of 10:54, 4 November 2021

Line 1:

{{Short description|Combinatorial optimization problem}}

The '''assignment problem''' is a fundamental [[combinatorial optimization]] problem. In its most general form, the problem is as follows:

:The problem instance has 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 agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the ''total cost'' of the assignment is to be minimized.

minimized.

Alternatively, describing the problem using graph theory: