Lecture 11

At the start of today's lecture I explained the Hungarian algorithm, which is a polynomial time algorithm for solving the assignment problem. My emphasis was on explaining why it works. In practice the algorithm looks rather different. The fact that one is adjusting node numbers and solving maximum matching problems is rather hidden from view.

You might like to read this nice tutorial on the Hungarian algorithm and read through the simple Example 2 on pages 18-27.

The algorithms in Lecture 11 are all polynomial time algorithms: Bellman-Ford, Dijkstra's and Prim's algorithms. They do involve numbers $c_{ij}$, but the the calculations that must be done with these numbers, such as adding (to find $c_{ij}+\lambda_j$) and comparing (to find $\min\{c_{it},c_{ij}+c_{jt}\}$) can all be done in time that is polynomial in the size of the input, as measured in numbers of binary bits. This is why running time is depends most crucially on the number of vertices $|V|$ and number of edges $|E|$.

One should be aware that for graphs with special structure, perhaps very sparse in edges, there exist specially tailored versions of some of our algorithms, which have better running time than those quoted in this lecture for a complete graph where $|E|=|V|^2$.

Examples sheet 1 #4

There was some question in the class about a part of the argument. Consider \begin{align} \max\;\{\; & 0^T x:\,Ax=b,\, x\geq 0\;\} \tag{1} \\ \min\;\{\; & y^T b:\, y^T A\geq 0^T\;\} \tag{2} \end{align} If (1) is feasible then for feasible $x,y$ we have $y^T b= (y^T A) x\geq 0$, so (2) is bounded.

On the other hand, if (2) is bounded then it is feasible and bounded. The strong duality theorem for linear programming states that (1) is feasible and bounded if and only if (2) is feasible and bounded. So (1) is feasible. This is enough to answer the question.

But how do we prove strong duality for linear programming? One way to prove it is via Farkas Lemma, which in the context of this question would be cheating. Another way is by appeal to the supporting hyperplane theorem and the sufficient conditions (satisfied by linear programs) for $\phi(b)$ to be convex.

I now think (c) of this question would be better phrased as "The Strong Duality theorem for linear programming states that if a linear programming problem is both feasible and bounded, then so is its dual." Show that this implies Farkas Lemma."

Lecture 10

I have been working on the notes for this lecture and have now added several further figures. Please make sure you have an up-to-date copy of the notes, as there were some errors in previous versions.

I will talk about the Hungarian algorithm for the assignment problem at the start of next lecture.

I mentioned that in a problem where all edge capacities are integers the Ford-Fulkerson algorithm runs in time $O(|E|\cdot f)$, where $f$ is some bound on the total flow. If edge capacities are not integers, one can still apply the Ford-Fulkerson algorithm, but it is not guaranteed to converge. There are examples in which one can increase flows on augmenting paths by ever smaller and smaller amounts, but not even converge to the optimal flow.

To understand the proofs of Hall's marriage theorem and Konig's theorem, you really need to sit down and carefully study for yourself an example, as I have now provided in Figure 12.

There are many nice applications in which the min-cut max-flow theorem can be used to obtain other results, by applying it to the right network. Another example of this is Menger's theorem: Let $G$ be a finite undirected graph and $x$ and $y$ two distinct vertices. Then the minimum number of edges whose removal disconnects $x$ and $y$ is equal to the maximum number of pairwise edge-independent paths from $x$ to $y$. This theorem is proved similarly to Konig's theorem.