Hungarian algorithm
The Hungarian algorithm, also known as the Hungarian method or Kuhn-Munkres algorithm, is a combinatorial optimization technique that solves the assignment problem by finding an optimal one-to-one matching between two finite sets of equal cardinality, such as assigning n agents to n tasks to minimize the total cost or maximize the total profit represented in a cost matrix.[1] Developed by American mathematician Harold W. Kuhn in 1955 and published in the Naval Research Logistics Quarterly, the algorithm draws its name from the earlier theoretical contributions of Hungarian mathematicians Dénes Kőnig, who in 1931 proved the König-Egerváry theorem relating vertex covers to matchings in bipartite graphs, and Jenő Egerváry, who extended these ideas to weighted graphs.[1] Kuhn's implementation translates these concepts into a practical procedure that anticipates primal-dual methods in linear programming, predating their formal development.[1] The method gained renewed interest in the mid-20th century through applications in operations research, including work by Merrill Flood and others on personnel assignment.[1] At its core, the algorithm proceeds in phases: it first reduces the cost matrix by subtracting the minimum value from each row and then each column to create zeros; next, it covers all zeros with the minimum number of horizontal and vertical lines; if the number of lines equals n, an optimal assignment can be selected by choosing independent zeros; otherwise, it adjusts the matrix by subtracting the smallest uncovered value from uncovered entries and adding it to doubly covered ones, repeating until optimality is achieved.[2] This process ensures a polynomial-time solution with a worst-case time complexity of O(n3), making it efficient for problems up to moderate sizes (n ≈ 1000), though implementations can vary in practice.[3] The algorithm's duality with linear programming formulations allows it to be viewed as a specialized simplex method for the transportation problem restricted to balanced bipartite graphs.[1] Beyond its foundational role in optimization, the Hungarian algorithm finds extensive applications in computer science and engineering, including task scheduling in operations research to minimize production costs, object tracking in computer vision via multi-target association, client selection in federated machine learning to optimize resource allocation, and multi-robot coordination in robotics for one-to-one task assignments under linear objectives.[4] Its robustness for small-to-medium bipartite matching problems has led to variants, such as dynamic versions for changing costs and parallel implementations for scalability, though it faces challenges in very large-scale settings due to cubic growth.[3]The Assignment Problem
Illustrative Example
Consider a simple assignment problem involving three workers (W1, W2, W3) and three tasks (T1, T2, T3), where the goal is to assign each worker to a unique task to minimize the total cost. The costs for assigning each worker to each task are given in the following matrix:| Worker | T1 | T2 | T3 |
|---|---|---|---|
| W1 | 25 | 44 | 36 |
| W2 | 28 | 41 | 40 |
| W3 | 23 | 50 | 35 |
- Row W1 minimum: 25, resulting row: [0, 19, 11]
- Row W2 minimum: 28, resulting row: [0, 13, 12]
- Row W3 minimum: 23, resulting row: [0, 27, 12]
| Worker | T1 | T2 | T3 |
|---|---|---|---|
| W1 | 0 | 19 | 11 |
| W2 | 0 | 13 | 12 |
| W3 | 0 | 27 | 12 |
- Column T1 minimum: 0, no change
- Column T2 minimum: 13, resulting column: [6, 0, 14]
- Column T3 minimum: 11, resulting column: [0, 1, 1]
| Worker | T1 | T2 | T3 |
|---|---|---|---|
| W1 | 0 | 6 | 0 |
| W2 | 0 | 0 | 1 |
| W3 | 0 | 14 | 1 |
| Worker | T1 | T2 | T3 |
|---|---|---|---|
| W1 | 25 | 44 | 36 |
| W2 | 28 | 41 | 40 |
| W3 | 23 | 50 | 35 |
Cost Matrix Formulation
The assignment problem can be formally defined using an n \times n cost matrix C = (c_{ij}), where c_{ij} represents the cost of assigning the i-th row entity (such as an agent or worker) to the j-th column entity (such as a task or job), for i, j = 1, \dots, n.[1] The objective is to find a one-to-one assignment that minimizes the total cost, formulated as the integer linear program: \min \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} subject to the constraints \sum_{j=1}^n x_{ij} = 1 \quad \forall i = 1, \dots, n, \quad \sum_{i=1}^n x_{ij} = 1 \quad \forall j = 1, \dots, n, \quad x_{ij} \in \{0, 1\} \quad \forall i, j, where x_{ij} = 1 if row i is assigned to column j, and x_{ij} = 0 otherwise.[5][1] These constraints ensure that each row and each column is assigned exactly once, corresponding to a perfect matching in the underlying structure.[1] This formulation assumes a balanced assignment problem, where the number of rows equals the number of columns (n agents and n tasks), resulting in a square cost matrix.[1] In the unbalanced case, where the numbers differ (e.g., more tasks than agents), the problem can be converted to a balanced one by introducing dummy rows or columns with zero costs to balance the matrix and account for unassigned entities at no additional cost, though the standard Hungarian algorithm targets the balanced scenario.[6] A brute-force approach to solving this problem requires evaluating all n! possible permutations of assignments to identify the minimum-cost one, yielding exponential time complexity that becomes impractical for even moderate n.[7] This motivates the development of polynomial-time algorithms like the Hungarian method to efficiently compute the optimal solution.[1]Bipartite Matching Formulation
The assignment problem is equivalently formulated as the problem of finding a minimum-weight perfect matching in a complete bipartite graph G = (U \cup V, E), where U and V are disjoint vertex sets each of size n, and E consists of all possible edges between U and V.[1] Each edge uv \in E is assigned a weight c_{uv}, corresponding to the cost of assigning the element from U to the element from V; for maximization objectives, weights can be negated to convert to a minimum-cost problem.[1] The objective is to select a matching M \subseteq E such that every vertex in U \cup V is incident to exactly one edge in M (a perfect matching, required since the graph is balanced with |U| = |V| = n), minimizing the total weight \sum_{(u,v) \in M} c_{uv}. This graph-theoretic perspective bridges the algebraic cost matrix representation to broader matching algorithms in combinatorial optimization. The algorithm solving this problem is commonly known as the Hungarian algorithm, or alternatively the Kuhn-Munkres algorithm, named after Harold W. Kuhn, who formalized it in 1955, and James Munkres, who provided a simplified version in 1957; the "Hungarian" moniker honors the foundational contributions of Hungarian mathematicians Dénes Kőnig and Jenő Egerváry to related matching theory.[1][8]Core Algorithm Concepts
Feasibility and Dual Variables
In the Hungarian algorithm, which solves the minimum cost perfect matching problem in a complete bipartite graph with vertex partitions U = \{u_1, \dots, u_n\} and V = \{v_1, \dots, v_n\} and nonnegative edge costs c_{uv}, feasible potentials are defined as real-valued labels y_u for each u \in U and z_v for each v \in V such that y_u + z_v \leq c_{uv} for all u \in U, v \in V. These potentials induce reduced costs \hat{c}_{uv} = c_{uv} - y_u - z_v \geq 0 for every edge, transforming the original cost matrix into a nonnegative equivalent while preserving optimality of solutions.[9] The equality subgraph associated with a set of feasible potentials includes only those edges (u, v) where the reduced cost vanishes, i.e., \hat{c}_{uv} = 0 or y_u + z_v = c_{uv}. A perfect matching within this subgraph identifies candidate assignments that are tight with respect to the potentials, forming the basis for primal feasibility in the algorithm's iterative process.[9] Feasible potentials correspond directly to the dual variables of the linear programming formulation of the assignment problem. The primal problem is \min \sum_{u \in U} \sum_{v \in V} c_{uv} x_{uv} subject to \sum_{v \in V} x_{uv} = 1 \quad \forall u \in U, \quad \sum_{u \in U} x_{uv} = 1 \quad \forall v \in V, \quad x_{uv} \geq 0 \quad \forall u,v. Its dual is \max \sum_{u \in U} y_u + \sum_{v \in V} z_v subject to y_u + z_v \leq c_{uv} \quad \forall u \in U, v \in V, with y_u, z_v unrestricted in sign; feasible potentials thus provide a feasible dual solution whose objective value lower-bounds the primal minimum cost. By the strong duality theorem for linear programs, optimal potentials achieve equality with the optimal assignment cost.[9][1] A simple initial feasible solution sets y_u = \min_{v \in V} c_{uv} for each u \in U and z_v = 0 for each v \in V, ensuring the dual constraints hold since the minimum over v is at most any specific c_{uv}. This initialization creates a starting equality subgraph with at least one zero per row, facilitating the algorithm's early iterations.[9]Equality Subgraph and Augmenting Paths
In the Hungarian algorithm for solving the minimum cost assignment problem on a bipartite graph with partitions U and V, the equality subgraph G_y is constructed using a set of feasible dual variables or potentials y_u for u \in U and y_v for v \in V, where y_u + y_v \leq c_{uv} for all edges (u,v). This subgraph includes all vertices U \cup V and only those edges where the reduced cost \hat{c}_{uv} = c_{uv} - y_u - y_v = 0, ensuring the edges represent zero-cost opportunities relative to the current potentials.[1][10] Within G_y, alternating paths are defined with respect to a partial matching M \subseteq E. An alternating path begins at an unmatched vertex in U and proceeds as a sequence of edges that alternate between non-matching edges (not in M) and matching edges (in M), all contained in G_y. These paths explore the structure of feasible zero-cost edges while respecting the current assignment constraints.[1] An augmenting path is a specific type of alternating path in G_y that terminates at an unmatched vertex in V. Augmenting along such a path involves taking the symmetric difference M \Delta P, which flips the matched and unmatched edges along P, thereby increasing the size of the matching by one without increasing the total cost, as all edges in P have zero reduced cost.[1][10] The Hungarian algorithm builds a maximum cardinality matching—and ultimately an optimal assignment—by repeatedly identifying and augmenting along these paths in the equality subgraph, adjusting the potentials when no further augmenting paths exist to enlarge the subgraph and create new zero-reduced-cost edges, until a perfect matching is obtained. This process leverages the zero-reduced-cost structure of G_y to ensure feasibility and optimality in the primal-dual framework.[1]Step-by-Step Algorithm in Bipartite Graphs
Initialization and Potential Adjustment
The Hungarian algorithm for solving the minimum cost assignment problem initializes the dual variables, or potentials, to establish a feasible starting point with non-negative reduced costs. The potentials for vertices in the left partition U are set to y_u = \min_{v \in V} c_{uv} for each u \in U, while the potentials for vertices in the right partition V are set to z_v = 0 for all v \in V. This ensures that the reduced costs c'_{uv} = c_{uv} - y_u - z_v \geq 0 for every edge (u,v), satisfying the dual feasibility constraints y_u + z_v \leq c_{uv}. The initial matching M is empty.[11] When no augmenting path is found in the equality subgraph during a search phase, the potentials are adjusted to enlarge the equality subgraph and restore the possibility of finding augmenting paths. The search builds a tree of reachable vertices from free U vertices. The adjustment computes \delta as the minimum reduced cost over edges from reached (visited) vertices in U to unreached vertices in V. The potentials are then updated by adding \delta to y_u for all reached vertices u \in U and subtracting \delta from z_v for all reached vertices v \in V. This uniform shift tightens edges in the search tree, making some previously non-tight edges tight (zero reduced cost), while preserving non-negativity of reduced costs elsewhere. The equality subgraph consists of tight edges (zero reduced cost) under the current potentials.[11] This update mechanism increases the dual objective \sum y_u + \sum z_v by n \delta (or adjusted for reached sets in some implementations), where n is the number of reached vertices, but ensures progress toward optimality by incorporating the slack. The process repeats until a perfect matching is found.[11]Finding and Augmenting Along Shortest Paths
In the Hungarian algorithm, finding an augmenting path occurs within the equality subgraph, which comprises all edges where the reduced cost c_{ij} - p_i - q_j = 0, with p_i and q_j denoting the dual potentials (also called labels) for vertices i \in U and j \in V, respectively.[11] This subgraph encodes feasible alternating paths relative to the current matching M, and the search begins from all free (unmatched) vertices in U.[11] To locate the shortest augmenting path—defined by the minimal number of edges, as all edges in the equality subgraph carry zero reduced cost—a breadth-first search (BFS) is employed, treating the subgraph as unweighted for path length purposes.[11] The BFS operates in layers: the initial layer includes all free U vertices, followed by reachable unmatched edges to V vertices, then backward along matched edges to U, and so forth, alternating directions to maintain the path's feasibility.[11] This layered approach handles multiple free vertices simultaneously by initiating the search from all of them as multi-sources, ensuring the first reachable free V vertex yields a shortest path without prioritizing one source over others.[11] Alternatively, for implementations emphasizing the weighted structure, a modified Dijkstra's algorithm can be applied directly on the residual graph with reduced costs as edge weights, where potentials serve as node labels to guarantee non-negativity (c_{ij} - p_i - q_j \geq 0 for forward edges and the negated for backward).[12] In this setup, the priority queue orders vertices by cumulative reduced cost distance from the sources (free U vertices), and the algorithm identifies the minimal-cost augmenting path. Potential adjustments from prior steps ensure no negative cycles or weights disrupt the search.[12] Upon discovering an augmenting path P from a free U vertex to a free V vertex, augmentation proceeds by symmetric difference: unmatched edges in P are added to M, and matched edges are removed, resulting in a new matching M \Delta P with cardinality |M| + 1.[11] This flip operation updates the assignment without altering the total cost under current potentials, as the path's reduced cost sums to zero. The process repeats in the same equality subgraph until no more augmenting paths exist, at which point potentials are adjusted if necessary.[11]Progress and Termination Guarantees
The Hungarian algorithm progresses by iteratively identifying and augmenting along shortest augmenting paths in the equality subgraph defined by the current dual variables, with each such augmentation strictly increasing the cardinality of the matching M by one.[11] In a balanced bipartite graph with n vertices per partition, this process performs at most n augmentations before attaining a perfect matching of size n. Multiple augmentations may occur in a single phase with fixed potentials until no more paths are found in the current equality subgraph.[11] When no augmenting path exists in the equality subgraph for the current phase, the dual variables y_u for left vertices and z_v for right vertices are updated using the minimum slack \delta from the search tree to maintain feasibility of the reduced costs c_{uv} - y_u - z_v \geq 0 for all edges. This adjustment raises the dual objective \sum y_u + \sum z_v by an amount related to \delta, which is positive and ensures new tight edges are created while preserving nonnegativity elsewhere.[11] The algorithm terminates when no augmenting path exists in the equality subgraph and all vertices are matched. At this point, M is a maximum matching by Berge's lemma, which asserts that a matching in a graph is maximum if and only if no augmenting path exists with respect to it. Moreover, the dual solution remains feasible, and complementary slackness holds: reduced costs are zero for all edges in M, and there are no zero-reduced-cost edges incident to unmatched vertices (though in perfect matching, none unmatched), equating the primal and dual objectives and confirming M's optimality.[11] Termination occurs after at most n augmentations, with phases bounded by the use of shortest paths to limit phase length. Each phase requires O(n^2) time to detect and trace augmenting paths via breadth-first search in the equality subgraph.[11] This bounded iteration count, combined with progress per phase, guarantees finite completion with an optimal assignment.[11]Time Complexity and Implementation
O(n^3) Implementation Details
The O(n³) implementation of the Hungarian algorithm operates on a complete bipartite graph with n vertices on each side, using dual variables (potentials) to maintain feasibility and compute reduced costs for edges. The algorithm consists of up to n phases, each finding a shortest augmenting path in the residual graph with respect to reduced costs and augmenting the matching along it; each phase requires O(n²) time for path finding and updates, yielding the overall O(n³) time complexity.[13] Key data structures include arrays for row potentials u and column potentials v (both of size n), a matching array pairU and pairV (size n) to track assignments, and temporary arrays such as way (size n) to reconstruct paths, used (size n) to mark visited columns, and minv (size n) for slack values. The cost matrix c (n × n) stores original edge weights, while reduced costs are computed on-the-fly as c'_{ij} = c_{ij} - u_i - v_j to ensure non-negativity, allowing efficient shortest path computations without explicit adjacency lists for dense graphs.[13] Slack variables in minv track the minimum reduced cost from the current search tree's frontier (unmatched rows) to each column j in the right partition V, updated during the path search to identify the bottleneck delta for potential adjustments. This enables a specialized O(n²) shortest path algorithm akin to Dijkstra, but implemented via iterative minimum selection over slacks rather than a full priority queue, avoiding logarithmic factors.[13] The main loop initializes feasible potentials (e.g., u_i = \min_j c_{ij}, v_j = 0) and an empty matching, then iterates until the matching size reaches n. In each phase, starting from a free row, the algorithm builds an alternating tree in the equality subgraph (edges with zero reduced cost), iteratively adjusting potentials by the minimum slack to expand the tree until an augmenting path to a free column is found, followed by augmentation and potential updates to ensure progress.[13] Potential updates occur after each augmentation by the minimum slack along the path, ensuring the equality subgraph grows and progress is made.[13]Incremental Addition of Assignments
The incremental variant of the Hungarian algorithm addresses dynamic scenarios where the assignment problem evolves by adding one new job (or worker) at a time to an existing bipartite graph, allowing reuse of the prior optimal matching and dual variables to avoid recomputing the entire solution from scratch. This approach begins with a solved k × k assignment problem, which provides an optimal matching and feasible dual potentials (labels) for the vertices. When adding the (k+1)th row and column—representing the new job and its associated costs to existing workers—the algorithm initializes the dual potentials for the new vertices based on maximum weight differences relative to the existing structure, ensuring initial feasibility. The previous matching remains partially valid, as it saturates the first k vertices on both sides, leaving only the new vertices unsaturated. To update the matching, the algorithm focuses computation on the new elements by constructing the equality subgraph using the reused potentials and searching for a single augmenting path that incorporates the new job, typically via a Hungarian tree rooted at the unsaturated new vertex. If no immediate path exists, potentials are adjusted by computing the minimum slack (the smallest difference between dual sums and edge costs) over relevant unmatched edges, which expands the equality subgraph and enables path discovery without altering the entire dual solution. This adjustment preserves the optimality of the prior matching while integrating the new assignment, resulting in a cardinality increase of one. The process re-runs only aspects involving the new column, leveraging the structure of the previous solution to limit exploration. The time complexity of this incremental addition is O(n²) per update in the worst case, where n is the current graph size, achieved through efficient slack maintenance and tree growth bounded by the graph's density; over n sequential additions starting from a 1 × 1 problem, the total complexity amortizes to O(n³), matching the standard Hungarian algorithm but offering efficiency for partial updates. Earlier implementations may exhibit O(n W) behavior if using unscaled shortest path methods with integer costs up to W, but polynomial-time scaling techniques, such as those employing Dijkstra's algorithm with potentials, ensure consistent O(n³) overall without dependence on cost magnitude. An improved variant further reduces average-case time to O(n) for certain configurations by optimizing dual initialization and path detection, though it falls back to O(n²) generally.[14] This incremental approach finds applications in online assignment scenarios, such as dynamic resource allocation in radar tracking systems where targets appear sequentially, or interactive topic modeling where mappings update based on user feedback without full recomputation. By enabling efficient handling of evolving inputs, it supports real-time decision-making in environments like scheduling or matching markets with arriving entities.[15][16]Theoretical Connections
Relation to Successive Shortest Paths
The assignment problem can be modeled as a minimum-cost flow problem in a bipartite flow network with unit capacities. A source vertex s is connected to each vertex in the left partition U by an edge of capacity 1 and cost 0; each vertex u \in U is connected to each vertex v \in V by an edge of capacity 1 and cost c_{uv}; and each vertex in the right partition V is connected to a sink vertex t by an edge of capacity 1 and cost 0. The goal is to compute a minimum-cost flow of value n = |U| = |V| from s to t. The successive shortest paths algorithm addresses this min-cost flow instance by beginning with a zero flow and repeatedly identifying the shortest s-t path in the residual graph, where edge costs are adjusted using node potentials to obtain non-negative reduced costs \bar{c}(i,j) = c(i,j) + \pi_i - \pi_j. Flow is augmented by 1 along this path, potentials are updated based on the path distances to preserve reduced cost non-negativity, and the process repeats for n iterations until the maximum flow is achieved. The Hungarian algorithm is equivalent to the successive shortest paths algorithm when specialized to this unit-capacity bipartite network for the assignment problem. The row and column potentials in the Hungarian method function as the node potentials \pi for reduced cost computations; the Hungarian reduced costs \bar{c}_{uv} = c_{uv} - u_u - v_v match the flow network's reduced costs on forward and backward residual edges. Furthermore, the equality subgraph in the Hungarian algorithm, formed by edges with zero reduced cost, corresponds exactly to the subgraph of zero-cost residual edges used to find shortest augmenting paths via breadth-first search.[17] This equivalence highlights how the Hungarian algorithm optimizes the successive shortest paths framework by exploiting the bipartite structure and unit capacities, thereby eliminating the need for general-purpose shortest path computations like Dijkstra's algorithm and focusing instead on efficient augmenting path searches within the equality subgraph to achieve O(n^3) time complexity without broader min-cost flow overhead.Linear Programming Duality Interpretation
The Hungarian algorithm for solving the assignment problem can be interpreted through the framework of linear programming (LP) duality, where the primal problem corresponds to finding a minimum-cost perfect matching in a bipartite graph, and the dual provides bounds via node potentials. The primal LP formulation is as follows: \begin{align*} \min &\quad \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} \\ \text{s.t.} &\quad \sum_{j=1}^n x_{ij} = 1 \quad \forall i = 1, \dots, n, \\ &\quad \sum_{i=1}^n x_{ij} = 1 \quad \forall j = 1, \dots, n, \\ &\quad x_{ij} \geq 0 \quad \forall i,j, \end{align*} where c_{ij} is the cost of assigning row i to column j, and x_{ij} indicates the assignment (with x_{ij} \in \{0,1\} for integral solutions). This LP has an integral optimal solution because the constraint matrix (the incidence matrix of the complete bipartite graph K_{n,n}) is totally unimodular, ensuring that the polytope defined by the constraints has integer vertices.[18][19] The associated dual LP is: \begin{align*} \max &\quad \sum_{i=1}^n y_i + \sum_{j=1}^n z_j \\ \text{s.t.} &\quad y_i + z_j \leq c_{ij} \quad \forall i,j = 1, \dots, n, \\ &\quad y_i, z_j \in \mathbb{R} \quad \forall i,j, \end{align*} where y_i and z_j represent unrestricted potentials (or labels) for rows and columns, respectively. By weak duality, any feasible primal solution provides an upper bound on the dual objective, and vice versa.[1][19] The Hungarian algorithm operates as a primal-dual method, maintaining a feasible primal solution (a partial matching, which is integral) and a feasible dual solution (feasible potentials y, z) throughout its execution. It iteratively augments the matching while adjusting the potentials to preserve dual feasibility, ensuring reduced costs c_{ij} - y_i - z_j \geq 0 for all edges. Upon termination with a perfect matching, strong duality holds with zero duality gap, as the primal and dual objectives equalize. This optimality is certified by complementary slackness conditions: for every assigned edge (i,j) with x_{ij} = 1, the dual constraint is tight (y_i + z_j = c_{ij}), and for every dual variable with positive contribution, the corresponding primal constraint is tight. These conditions align the algorithm's potential adjustments with the economic interpretation of dual variables as shadow prices in assignment markets.[1][19] This duality perspective traces back to foundational work by John von Neumann, whose 1953 analysis of expanding economies in the second edition of Theory of Games and Economic Behavior (co-authored with Oskar Morgenstern) applied similar dual formulations to assignment-like problems in resource allocation, influencing the development of primal-dual algorithms for combinatorial optimization.[20]Matrix-Based Algorithm Description
Initial Reduction Steps
The initial reduction steps of the Hungarian algorithm prepare the cost matrix for the assignment problem, which involves assigning n workers to n tasks to minimize total cost, represented by an n × n matrix C where c_{ij} denotes the cost of assigning worker i to task j. These steps transform the original matrix into a reduced form with non-negative entries and zeros indicating potential optimal assignments, without altering the optimal solution set.[21] In the first step, row reduction is performed by identifying the minimum entry in each row of the cost matrix and subtracting this minimum value from every element in that row. This operation ensures that at least one zero appears in each row, as the smallest entry becomes zero while all others remain unchanged or increase relative to it. For example, consider a 3 × 3 cost matrix:| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Worker 1 | 5 | 9 | 2 |
| Worker 2 | 6 | 7 | 4 |
| Worker 3 | 8 | 3 | 1 |
| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Worker 1 | 3 | 7 | 0 |
| Worker 2 | 2 | 3 | 0 |
| Worker 3 | 7 | 2 | 0 |
| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Worker 1 | 1 | 5 | 0 |
| Worker 2 | 0 | 1 | 0 |
| Worker 3 | 5 | 0 | 0 |