Content deleted Content added
Tag: Reverted |
→See also: Correct name of stable matching problem |
||
| (31 intermediate revisions by 25 users not shown) | |||
Line 1:
{{Short description|Combinatorial optimization problem}}
[[File:hungarian_algorithm_unbalanced_assignment_problem_example.svg|thumb|upright=2|Worked example of assigning tasks to an unequal number of workers using the [[Hungarian method]]]]
The '''assignment problem''' is a fundamental [[combinatorial optimization]] problem. In its most general form, the problem is as follows:
:The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any task, incurring some ''cost'' that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the ''total cost'' of the assignment is minimized.
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-cost perfect matching'''. Otherwise, it is called '''unbalanced assignment'''.<ref name=":0">{{Cite web|url=https://www.
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 12 ⟶ 15:
Now, suppose that there are ''four'' taxis available, but still only three customers. This is an ''unbalanced assignment'' problem. One way to solve it is to invent a fourth dummy task, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. This reduces the problem to a balanced assignment problem, which can then be solved in the usual way and still give the best solution to the problem.
Similar adjustments can be done in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.
Line 20 ⟶ 21:
The formal definition of the '''assignment problem''' (or '''linear assignment problem''') is
:Given two sets, ''A'' and ''T''
::<math>\sum_{a\in A}C(a,f(a))</math>
:is minimized.▼
▲is minimized.
Usually the weight function is viewed as a square real-valued [[matrix (mathematics)|matrix]] ''C'', so that the cost function is written down as:
Line 32:
==Algorithms==
A naive solution for the assignment problem is to check all the assignments and calculate the cost of each one. This may be very inefficient since, with ''n'' agents and ''n'' tasks, there are ''n''! ([[factorial]] of ''n'') different assignments.
Another naive solution is to greedily assign the pair with the smallest cost first, and remove the vertices; then, among the remaining vertices, assign the pair with the smallest cost; and so on. This algorithm may yield a non-optimal solution. For example, suppose there are two tasks and two agents with costs as follows:
The assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], each specialization has a small solution space and thus more efficient algorithms designed to take advantage of its special structure.▼
* Alice: Task 1 = 1, Task 2 = 2.
* George: Task 1 = 5, Task 2 = 8.
The greedy algorithm would assign Task 1 to Alice and Task 2 to George, for a total cost of 9; but the reverse assignment has a total cost of 7.
▲Fortunately, there are many algorithms for finding the optimal assignment in time [[polynomial time|polynomial]] in ''n''. The assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], or in worst-case polynomial time using the [[ellipsoid method]], each specialization has a
=== Balanced assignment ===
In the balanced assignment problem, both parts of the bipartite graph have the same number of vertices, denoted by ''n''.
One of the first polynomial-time algorithms for balanced assignment was the [[Hungarian algorithm]]. It is a ''global'' algorithm – it is based on improving a matching along augmenting paths (alternating paths between unmatched vertices). Its run-time complexity, when using [[Fibonacci heap]]s, is <math>O(mn + n^2\log n)</math>,<ref>{{Cite journal|last1=Fredman|first1=Michael L.|last2=Tarjan|first2=Robert Endre|date=1987-07-01|title=Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms|journal=J. ACM|volume=34|issue=3|pages=596–615|doi=10.1145/28869.28874|s2cid=7904683|issn=0004-5411|doi-access=free}}</ref> where ''m'' is a number of edges. This is currently the fastest run-time of a [[strongly polynomial]] algorithm for this problem. Some variants of the Hungarian algorithm also benefit from parallel computing, including GPU acceleration.<ref>{{Cite journal |last=Kawtikwar |first=Samiran |last2=Nagi |first2=Rakesh |date=2024-05-01 |title=HyLAC: Hybrid linear assignment solver in CUDA |url=https://linkinghub.elsevier.com/retrieve/pii/S0743731524000029 |journal=Journal of Parallel and Distributed Computing |volume=187 |pages=104838 |doi=10.1016/j.jpdc.2024.104838 |issn=0743-7315|doi-access=free }}</ref> If all weights are integers, then the run-time can be improved to <math>O(mn + n^2\log \log n)</math>, but the resulting algorithm is only weakly-polynomial.<ref>{{Cite journal|last=Thorup|first=Mikkel|date=2004-11-01|title=Integer priority queues with decrease key in constant time and the single source shortest paths problem|journal=Journal of Computer and System Sciences|series=Special Issue on STOC 2003|volume=69|issue=3|pages=330–353|doi=10.1016/j.jcss.2004.04.003|issn=0022-0000|doi-access=free}}</ref> If the weights are integers, and all weights are at most ''C'' (where ''C''>1 is some integer), then the problem can be solved in <math>O(m\sqrt{n} \log(n\cdot C))</math> weakly-polynomial time in a method called ''weight scaling''.<ref>{{Cite journal|last1=Gabow|first1=H.|last2=Tarjan|first2=R.|date=1989-10-01|title=Faster Scaling Algorithms for Network Problems|journal=SIAM Journal on Computing|volume=18|issue=5|pages=1013–1036|doi=10.1137/0218069|issn=0097-5397}}</ref><ref>{{Cite journal|last1=Goldberg|first1=A.|last2=Kennedy|first2=R.|date=1997-11-01|title=Global Price Updates Help|journal=SIAM Journal on Discrete Mathematics|volume=10|issue=4|pages=551–572|doi=10.1137/S0895480194281185|issn=0895-4801}}</ref><ref>{{Cite journal|last1=Orlin|first1=James B.|last2=Ahuja|first2=Ravindra K.|date=1992-02-01|title=New scaling algorithms for the assignment and minimum mean cycle problems|journal=Mathematical Programming|language=en|volume=54|issue=1–3|pages=41–56|doi=10.1007/BF01586040|s2cid=18213947|issn=0025-5610}}</ref>
In addition to the global methods, there are ''local methods'' which are based on finding local updates (rather than full augmenting paths). These methods have worse asymptotic runtime guarantees, but they often work better in practice. These algorithms are called [[auction algorithm]]s, push-relabel algorithms, or preflow-push algorithms. Some of these algorithms were shown to be equivalent.<ref>{{Cite
Some of the local methods assume that the graph admits a ''perfect matching''; if this is not the case, then some of these methods might run forever.<ref name=":0" />{{Rp|3}} A simple technical way to solve this problem is to extend the input graph to a ''complete bipartite graph,'' by adding artificial edges with very large weights. These weights should exceed the weights of all existing matchings, to prevent appearance of artificial edges in the possible solution.
As shown by Mulmuley, Vazirani and Vazirani,<ref>{{Cite journal|last1=Mulmuley|first1=Ketan|last2=Vazirani|first2=Umesh|author-link2=Umesh Vazirani|last3=Vazirani|first3=Vijay|author-link3=Vijay Vazirani|year=1987|title=Matching is as easy as matrix inversion|journal=Combinatorica|volume=7|issue=1|pages=105–113|doi=10.1007/BF02579206|s2cid=47370049|author-link1=Ketan Mulmuley}}</ref> the problem of minimum weight perfect matching is converted to finding minors in the [[adjacency matrix]] of a graph. Using the [[isolation lemma]], a minimum weight perfect matching in a graph can be found with probability at least
=== Unbalanced assignment ===
Line 65 ⟶ 72:
The total weight of the matching is: <math>\sum_{(i,j)\in A\times T} w_{ij}x_{ij}</math>. The goal is to find a maximum-weight perfect matching.
To guarantee that the variables indeed represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i.e.,
<math display="block">\sum_{j\in T}x_{ij}=1\text{ for }i\in A, \,
~~~
Line 77 ⟶ 84:
\sum_{i\in A}x_{ij}=1\text{ for }j\in T </math><math display="block">0\le x_{ij}\le 1\text{ for }i,j\in A,T, \, </math><math display="block">x_{ij}\in \mathbb{Z}\text{ for }i,j\in A,T. </math>This is an integer linear program. However, we can solve it without the integrality constraints (i.e., drop the last constraint), using standard methods for solving continuous linear programs. While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values. This is because the constraint matrix of the fractional LP is [[Unimodular matrix#Total unimodularity|totally unimodular]] – it satisfies the four conditions of Hoffman and Gale.
=== Other methods and approximation algorithms===▼
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://
== 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:
▲=== Other methods and approximation algorithms===
* Layer 1: One source-node '''s'''.
▲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.
* 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.
== 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]].
Line 102 ⟶ 114:
*[[Rank-maximal matching]]
*[[Secretary problem]]
*[[Stable
*[[Stable roommates problem]]
*[[Weapon target assignment problem]]
| |||