The assignment problem chooses a one-to-one pairing of jobs and agents minimizing their total cost. Its minimum-cost flow formulation puts unit supplies on job vertices and unit demands on agent vertices of a bipartite graph. Integral feasible flows are perfect matchings.
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.
These feasible potentials give the lower bound on every assignment cost. An assignment using only equality edges attains this bound and is optimal by weak duality and complementary slackness.
Articles by others on the same topic
The Assignment Problem is a fundamental problem in combinatorial optimization that involves assigning a set of resources to a set of tasks in such a way that the total cost is minimized (or, in some cases, maximized). It can be represented mathematically and is commonly solved using various optimization techniques.