Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
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.
== 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.
| |||