\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt}
\begin{center} Lecture 8: Basic Flow Algorithms and Capacity Scaling \end{center}

Today: From flow optimality conditions to flow algorithms.

Recap of Last Lecture

Last time: Maximum flow problem: Important concepts: Key theorem: Max-Flow Min-Cut duality: The following statements are equivalent:

Maximum Flow Algorithms

We understand now the optimality conditions for maximum flow well. But how about computing one? Observe: The Max-Flow Min-Cut theorem can be easily turned into an actual algorithm.

Computing Max Flow with Augmenting Paths

Natural algorithm: Repeatedly find augmenting paths in the residual graph. Sidenote: The above algorithm was simple to describe but its dynamics can be quite complex.

Maximum Bottleneck Capacity Augmenting Paths

So far, we assumed that we just find an augmenting path. But maybe there is a “smart” way to choose one? Natural idea: Always choose an augmenting path $P$ that has maximum bottleneck capacity $u_f(P)$.

From now on: Unless stated otherwise, we assume that capacities are integral.

Scaling Technique

Idea of maximum bottleneck capacity augmenting was to be greedy

Another approach: Scaling.

One can think of scaling as a reverse process to rounding.

Big benefit: Fixing up the solution often correspond to solving the original problem in “unit case”. (We, in a sense, reduce the general case to unit case.)

How to apply this approach to the maximum flow problem?