Editing Assignment problem (section)

== Many-to-many assignment{{Anchor|mtm}} ==
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 capacity 1.
* 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.