Execute a single phase of the algorithm. A phase of the Hungarian
algorithm consists of building a set of committed workers and a set of
committed jobs from a root unmatched worker by following alternating
unmatched/matched zero-slack edges. If an unmatched job is encountered,
then an augmenting path has been found and the matching is grown. If the
connected zero-slack edges have been exhausted, the labels of committed
workers are increased by the minimum slack among committed workers and
non-committed jobs to create more zero-slack edges (the labels of
committed jobs are simultaneously decreased by the same amount in order
to maintain a feasible labeling).
The runtime of a single phase of the algorithm is O(n^2), where n is the
dimension of the internal square cost matrix, since each edge is visited
at most once and since increasing the labeling is accomplished in time
O(n) by maintaining the minimum slack values among non-committed jobs.
When a phase completes, the matching will have increased in size.
Execute a single phase of the algorithm. A phase of the Hungarian algorithm consists of building a set of committed workers and a set of committed jobs from a root unmatched worker by following alternating unmatched/matched zero-slack edges. If an unmatched job is encountered, then an augmenting path has been found and the matching is grown. If the connected zero-slack edges have been exhausted, the labels of committed workers are increased by the minimum slack among committed workers and non-committed jobs to create more zero-slack edges (the labels of committed jobs are simultaneously decreased by the same amount in order to maintain a feasible labeling).
The runtime of a single phase of the algorithm is O(n^2), where n is the dimension of the internal square cost matrix, since each edge is visited at most once and since increasing the labeling is accomplished in time O(n) by maintaining the minimum slack values among non-committed jobs. When a phase completes, the matching will have increased in size.