\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt}

Combinatorial Optimization: Finding Optimum Solution

Maximum Flow


Tarjan: Data Structures and Network Algorithms

Ford and Fulkerson, Flows in Networks, 1962 (paper 1956)

Ahuja, Magnanti, Orlin Network Flows. Problem: do min-cost.

Problem: in a graph, find a flow that is feasible and has maximum value.

Directed graph, edge capacities $u(e)$ or $u(v,w)$. Why not $c$? reserved for costs, later. source $s$, sink $t$

Goal: assign a flow value to each edge:

Alternative: (net flow form)

Net flow cleaner for math but involves negative flows and makes lower-bound flows messy. Raw flow may fit intuition/reality better.

Water hose intuition. Also routing commodities, messages under bandwidth constraints, etc. Often “per unit time” flows/capacities.

Maximum flow problem: find flow of maximum value.

Path decomposition (another perspective):

Point A. 15 min to here.
2014 Lec 8 start

Decision question: is there nonzero feasible flow

What about max-flow?

Suppose have some flow. How can we send more?

We have proven Max-flow Min-cut duality:


Another cute corollary:

Note that max-flow and min-cut are witnesses to each others' optimality.