Content deleted Content added
m Open access bot: url-access updated in citation with #oabot. |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (One intermediate revision by one other user not shown) | |||
Line 89:
== 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|url-access=subscription }}</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:
Line 114:
*[[Rank-maximal matching]]
*[[Secretary problem]]
*[[Stable
*[[Stable roommates problem]]
*[[Weapon target assignment problem]]
| |||