# A General Statistical Physics Framework for Assignment Problems
## 6 Examples
We considered all \(p_{max}(i)\) to be equal to a given value \(p\) and ran Matching with \(p\) varying from 1 to \(k\). Note that both matrices \(C_{1}\) and \(C_{2}\) contain cycles. As such, optimal assignments based on those matrices are not unique. To remove the degeneracy, we added random uniform noise between \([0,\epsilon]\) with \(\epsilon=0.001\) to all values of the cost matrices (see Section 4 for details). The Hungarian algorithm remains a standard for solving balanced as well as unbalanced assignment problems. It needs to be adapted, however, when solving multi-task assignment problems. The corresponding textbook solution that was used, for example, in Ref. [14] is to make copies or clones of the agents, solve the augmented unbalanced assignment problem using the Hungarian algorithm, and then regroup all clones of an agent to define the tasks that it is assigned to. We consequently created multiple versions of the cost matrices \(C_{1}\) and \(C_{2}\), with all agents copied \(p\) times, where \(p\) defines the maximum number of tasks that an agent can perform. We ran our own version of the Hungarian algorithm on those matrices. This version is adapted from the serial code written by [PERSON] and is publicly available at [[https://github.com/mcximing/hungarian-algorithm-cpp](https://github.com/mcximing/hungarian-algorithm-cpp)]([https://github.com/mcximing/hungarian-algorithm-cpp](https://github.com/mcximing/hungarian-algorithm-cpp)), (accessed on 1 May 2021). Comparisons of the results of Matching, of the Hungarian algorithm, and of previous studies are provided in Table 4 for the cost matrix \(C1\) and in Table 5 for the cost matrix \(C2\). \begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline
**Method \(\backslash\)\(p\)1 [FOOTNOTE:1]Footnote 1: Each agent is allowed to execute up to \(p\) tasks. Note that as there are 8 tasks and 5 agents only, the minimum value of \(p\) is 2 if all the tasks must be executed. 2 Genetic algorithm [26]. 3 Note available in either [26] or [13]. 4 Ant colony algorithm [13]. 5
& **2** & **3** & **4** & **5** & **6** & **7** & **8** \\ \hline Matching, \(p_{min}=1\) & 1520 & 1470 & 1450 & 1450 & 1450 & 1450 & 1450 \\ Matching, \(p_{min}=0\) & 1520 & 1470 & 1440 & 1420 & 1410 & 1400 & 1400 \\ Hungarian & 1520 & 1470 & 1440 & 1420 & 1410 & 1400 & 1400 \\ Majumdar GA2  & 1520 & 1470 & 1450 & NA & NA & NA & NA \\ Wang AC3  & 1520 & 1470 & 1450 & NA & NA & NA & NA \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Solving the multi-task assignment problems defined by the cost matrix \(C_{1}\). \begin{table}
\begin{tabular}{c c c} \hline \hline \(p_{min}=0\) & \(p_{min}=1\) & Wang a  \\ \hline \(A_{1}\to T_{3}\) & \(A_{1}\to T_{3}\) & \(A_{1}\to T_{3}\) \\ \(A_{2}\to T_{4}\), \(T_{8}\) & \(A_{2}\to T_{8}\) & \(A_{2}\to T_{8}\) \\ \(A_{3}\) & \(A_{3}\to T_{4}\) & \(A_{3}\to T_{4}\) \\ \(A_{4}\to T_{7}\) & \(A_{4}\to T_{7}\) & \(A_{4}\to T_{7}\) \\ \(A_{5}\to T_{1}\), \(T_{2}\), \(The results of Matching have been proven to be optimal (see Section 3). As expected, those results are strongly dependent on the constraints imposed on the problem: we can find assignments with a lower total cost if we allow agents to remain idle by setting \(p_{min}\) to 0. For example, for the cost matrix \(C_{1}\), in the extreme case with \(p_{min}=0\) and \(p_{max}=8\) for all agents, we find that all eight tasks have been assigned to agent 5, while the other agents have no task to perform, with a total cost of 1400. If instead we set \(p_{min}=1\) and keep \(p_{max}=8\), we find that agent 5 is assigned tasks 1, 2, 5, and 6; agent 1 is assigned task 3; agent 2 is assigned task 8; agent 3 is assigned task 4; and agent 4 is assigned task 7, for a total cost of 1450. If we instead run the Hungarian algorithm with agents that have been cloned to allow for multi-task assignments, we find optimal assignments that match those found by Matching with \(p_{min}\) set to 0 for both cost matrices.