The Hungarian algorithm maintains feasible assignment dual potentials and a matching of equality edges. If the alternating search cannot augment, adjust reachable job and agent potentials by the smallest reduced cost leaving the search set. This preserves feasibility and existing matching equalities while exposing a new equality edge. A resulting perfect matching attains the dual lower bound.
The Hungarian algorithm is a combinatorial optimization algorithm used to solve the assignment problem, which involves finding the optimal way to assign a set of tasks to a set of agents such that the total cost is minimized. The assignment problem can be represented mathematically using a cost matrix, where each element represents the cost of assigning a particular task to a particular agent.
New to topics? Read the docs here!