Content deleted Content added
rmv long term sock edits |
Erel Segal (talk | contribs) lead section |
||
Line 7:
: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.
If the numbers of agents and tasks are equal, then the problem is called '''balanced assignment''', and the graph-theoretic version is called '''minimum cost perfect matching'''. 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. ==Examples==
Line 91 ⟶ 93:
Another generalization of the assignment problem is extending the number of sets to be matched from two to many. So that rather than matching agents to tasks, the problem is extended to matching agents to tasks to time intervals to locations. This results in [[Multidimensional assignment problem (MAP)]].
=== Many-to-many assignment ===
In the original assignment problem
==See also==
| |||