Assignment problem: Difference between revisions

Revision as of 05:39, 29 July 2024

Revision as of 11:41, 29 July 2024

Line 1:

{{Short description|Combinatorial optimization problem}}

[[File:hungarian_algorithm_unbalanced_assignment_problem_example.svg|thumb|upright=2|Worked example of assigning tasks to an unequal number of workers using the [[Hungarian method]]]]

The '''assignment problem''' is a fundamental [[combinatorial optimization]] problem<ref>{{Cite web |title=The Assignment Problem |url=https://www.cs.emory.edu/~cheung/Courses/253/Syllabus/Assignment/intro.html#:~:text=The%20assignment%20problem%20is%20one,in%20a%20weighted%20bipartite%20graph. |access-date=2024-07-29 |website=www.cs.emory.edu}}</ref>. 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 minimized.

Alternatively, describing the problem using graph theory:

:The assignment problem consists of finding, in a [[weighted graph|weighted]] [[bipartite graph]], a [[Matching (graph theory)|matching]] of a given size, in which the sum of weights of the edges is minimum.<ref>{{Cite book |last=Patriksson |first=Michael |url=https://www.google.com.vn/books/edition/The_Traffic_Assignment_Problem/vLnQBQAAQBAJ?hl=vi&gbpv=1&dq=%22Assignment+problem%22&pg=PA207&printsec=frontcover |title=The Traffic Assignment Problem: Models and Methods |date=2015-02-18 |publisher=Courier Dover Publications |isbn=978-0-486-78790-9 |language=en}}</ref><ref>{{Cite web |title=Dịch vụ viết thuê assignment |url=https://luanvan1080.com/dich-vu-nhan-viet-lam-thue-assignment-uy-tin.html |access-date=2024-07-29 |website=Luanvan1080 |language=vi}}</ref>

If the numbers of agents and tasks are equal, then the problem is called ''balanced assignment''. Otherwise, it is called ''unbalanced assignment''.<ref name=":0">{{Cite web|url=https://www.labs.hpe.com/techreports/2012/HPL-2012-40.pdf|title=On minimum-cost assignments in unbalanced bipartite graphs|last=Lyle Ramshaw, Robert E. Tarjan|date=2012|website=HP research labs}}</ref> If 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''. Commonly, when speaking of the ''assignment problem'' without any additional qualification, then the ''linear balanced assignment problem'' is meant.