2
$\begingroup$

When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and columns.

However, in section 17.2 of the book, Combinatorial optimization polyhedra and efficiency by Schrijver, a seemingly different algorithm is presented. Here, we start with a matching $M$, assign $W_M$ and $U_M$ as the edges on the left and right of the bi-partite graph that haven't been covered by the matching, describe path lengths as $l_e=w_e$ if the edge is in $M$ and $l_e=-w_e$ otherwise and find a min path from $U_M$ to $W_M$. Then, reset $M$ to $M'$, the symmetric difference between the path $P$ and $M$.

These two algorithms seem very different to me. Are they somehow the same under the cover?

$\endgroup$

1 Answer 1

1
$\begingroup$

Full disclosure, my understanding is kind of vague, and I don't have access to the book you mentioned, so my graph based variant is probably a little different from yours. But I spent several days trying to find out how the different variants of this algorithm relate to each other, and a post like this would have really helped me. Hopefully it does help someone.

The matrix based algorithm goes as follows:

  1. Subtract (and note) row minima from the rows; then subtract (and note) column minima from the columns; After this step, there is at least one zero in every row and every column. Note, that any optimal assignment in the original matrix is still optimal in the new one.
  2. Cover the zeros with minimal number of lines.
  3. If the minimal number of lines is $n$, the optimal solution has been found.
  4. If the number of lines necessary is less than $n$, we need to manipulate the cost matrix. Find the minimum over the uncovered elements, then add this value to each covered column and subtract it from each uncovered row; then, go back to 2)

The graph based variant of the algorithm:

  1. Label the vertices such that: $p(i) = min \left( c_{i, j} \right) \forall i \in X$ and $p(j) = min \left( c_{i, j} - p(i)\right) \forall j \in Y$.
  2. Construct a new bipartite graph $G_p$, where $(i, j) \in E$ if $c_{i, j} - p(i) - p(j) = 0$
  3. Find the perfect matching in $G_p$.
  4. If the size of the matching is $n$, the optima solution has been found.
  5. If not, we need to change the labels of the vertices. Find a set in $G_p$ $A \subset X$ such that $|A| > N(A)$ where $N(A)$ denotes the neighbors of $A$ (such a set always exists, Hall theorem). Find $d = min \{c_{i,j} - p(i) - p(j) | i \in A, j \notin N(A) \}$. Then we change the labels: $p(i) := p(i) + d \forall i \in A$ and $p(j) := p(j) + d \forall j \in N(A)$, and then continue with 3)

The greatest difference is in the covering of zeros vs. constructing a matching steps. But, since the cost matrix is still a representation of a graph, we can interpret the covering of zeros as an operation on that graph. Each zero in the graph corresponds exactly to an edge $(i, j)$ in the new graph $G_p$ constructed by the graph based algorithm.

Covering the zeros then corresponds to construction of a vertex cover. If the zero is covered by a horizontal line, that means the vertex $i \in X$ has been added to the cover, if by a vertical line, the vertex $j \in Y$. Because each line corresponds to a specific task, covering a zero by a horizontal line means that the task has been assigned. Covering a zero by a vertical line means that the worker (column) has been assigned a task. Finding a minimal number of lines necessary corresponds to finding a minimal vertex cover, which in bipartite graphs is exactly equal to the size of the maximal matching (König theorem).

You could also cover by crosses instead of lines. Each cross then corresponds to an assignment of a worker to a task (1 to 1), and you have to maximize the number of crosses instead of minimizing. This then corresponds to a matching in the bipartite graph.

As far as I can tell, there are several ways to do the cost manipulation and I don't understand this enough to be able to explain why they work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.