Content deleted Content added
Erel Segal (talk | contribs) lead section |
Erel Segal (talk | contribs) |
||
Line 5:
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
If the numbers of agents and tasks are equal, then the problem is called '''balanced assignment''', and the graph-theoretic version is called '''minimum
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.
Line 88:
Other approaches for the assignment problem exist and are reviewed by Duan and Pettie<ref>{{Cite journal|last1=Duan|first1=Ran|last2=Pettie|first2=Seth|date=2014-01-01|title=Linear-Time Approximation for Maximum Weight Matching|url=https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf|journal=Journal of the ACM|volume=61|pages=1–23|language=EN|doi=10.1145/2529989|s2cid=207208641}}</ref> (see Table II). Their work proposes an [[approximation algorithm]] for the assignment problem (and the more general [[maximum weight matching]] problem), which runs in linear time for any fixed error bound.
==
In the basic assignment problem, each agent is assigned to at most one task and each task is assigned to at most one agent. In the '''many-to-many assignment problem''',<ref>{{Cite journal |last=Zhu |first=Haibin |last2=Liu |first2=Dongning |last3=Zhang |first3=Siqin |last4=Zhu |first4=Yu |last5=Teng |first5=Luyao |last6=Teng |first6=Shaohua |date=2016-03-07 |title=Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking |url=https://www.sciencedirect.com/science/article/pii/S0304397516000037 |journal=Theoretical Computer Science |volume=618 |pages=30–41 |doi=10.1016/j.tcs.2016.01.002 |issn=0304-3975}}</ref> each agent ''i'' may take up to ''c<sub>i</sub>'' tasks (''c<sub>i</sub>'' is called the agent's ''capacity''), and each task ''j'' may be taken by up to ''d<sub>j</sub>'' agents simultaneously (''d<sub>j</sub>'' is called the task's ''capacity''). If the sums of capacities in both sides are equal (<math>\sum_i c_i = \sum_j d_j</math>), then the problem is ''balanced'', and the goal is to find a perfect matching (assign exactly ''c<sub>i</sub>'' tasks to each agent ''i'' and exactly ''d<sub>j</sub>'' agents to each task ''j'') such that the total cost is as small as possible.
The problem can be solved by reduction to the [[Network flow problem|minimum cost network flow problem]].<ref>{{Cite web |last=D.W. |title=High-multiplicity maximum-weight matching |url=https://cs.stackexchange.com/questions/161149/high-multiplicity-maximum-weight-matching/161151#161151 |access-date=2025-01-15 |website=Computer Science Stack Exchange |language=en}}</ref> Construct a flow network with the following layers:
* Layer 1: One source-node '''s'''.
* Layer 2: a node for each agent. There is an arc from '''s''' to each agent ''i'', with cost 0 and capacity ''c<sub>i</sub>'' .
* Level 3: a node for each task. There is an arc from each agent ''i'' to each task ''j'', with the corresponding cost, and infinite capacity.
* Level 4: One sink-node '''t'''. There is an arc from each task to '''t''', with cost 0 and capacity ''d<sub>j</sub>''.
An integral maximum flow of minimum cost can be found in polynomial time; see [[network flow problem]]. Every integral maximum flow in this network corresponds to a matching in which at most ''c<sub>i</sub>'' tasks are assigned to each agent ''i'' and at most ''d<sub>j</sub>'' agents are assigned to each task ''j'' (in the balanced case, exactly ''c<sub>i</sub>'' tasks are assigned to ''i'' and exactly ''d<sub>j</sub>'' agents are assigned to ''j''). A min-cost maximum flow corresponds to a min-cost assignment.
==Generalization==
When phrased as a graph theory problem, the assignment problem can be extended from [[bipartite graph]]s to arbitrary graphs. The corresponding problem, of finding a [[matching (graph theory)|matching]] in a [[weighted graph]] where the sum of weights is maximized, is called the [[maximum weight matching|maximum weight matching problem]].
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)]].
==See also==
| |||