\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt}
\begin{center} Lecture 9: Advanced Max Flow Algorithm \end{center}

Different Variants of the Max Flow Problem

So far, we were focused on the “canonical” maximum flow problem formulation. In some of the applications though, one needs to solve different variants of this problem. Amazing thing about the maximum flow problem is that many of these, seemingly, more general variants can be reduced to the “canonical” problem.

Some examples:

Strongly Polynomial Max Flow Algorithm

Our New Goal: Design an augmenting path based algorithm that aims to increase the $s$-$t$ distance $d_f(s,t)$ in the residual graph. (Instead of trying to directly push as much flow "as possible” in each iteration - which was the case before in the maximum bottleneck capacity augmenting path algorithm.)