Interesting applications of max-flow and linear programming

Max-flow and linear programming are two big hammers in algorithm design: each are expressive enough to represent many poly-time solvable problems. Some problems are obvious applications of max-flow: like finding a maximum matching in a graph. What I'm looking for are examples of problems that can be solved via clever encodings as flow problems or LP problems -- ones that aren't obvious. I'm looking for questions at a level suitable for a homework problem for an advanced undergraduate or beginning graduate course in algorithms.

Any ideas?

-

Determining whether a sports team has been mathematically eliminated from qualifying for the playoffs is a cute application of max-flow min-cut:

http://www.cs.princeton.edu/courses/archive/spr03/cs226/assignments/baseball.html

-

Another interesting application of LP is finding Nash equilibrium for a two player zero-sum game.

http://en.wikipedia.org/wiki/Zero-sum_game#Solving

-

The algorithms book by Kleinberg and Tardos has a number of such examples, including the baseball elimination one. It has a flight scheduling example that I've used in class - the graph cut example is also easy to explain. The problems have many more.

The examples work, in that students tend to have 'aha' moments (or so they tell me).

-

You can prove the Birkhoff-von Neumann theorem directly with linear programming. Depending on your taste it is a quite elegant way to prove that result. There are basically two ways - one to use the conditions for a vertex of a polytope given by constraints to show that a doubly stochastic matrix which is a vertex of the Birkhoff polytope must have a row or column with only one nonzero entry, then induce. This does not use the full "fundamental theorem of linear programming".

The other approach is to observe that at a vertex there is a full dimensional set of linear objectives for which the vertex is optimal, formulate the dual program and then show that the 2n unconstrained dual variables lie on an n dimensional space; complementary slackness then shows that the primal variable has only n nonzero elements, double stochasticity then guarantees there must be one in each row, one in each column, and each must be unity - therefore a permutation matrix. Obviously this approach really does exploit the linear program structure, if that is what you want to teach.

I came up with this myself so don't know of an actual reference, but it should not be that novel.

You can also prove Birkhoff-von Neumann are a max flow/min cut theorem (which is pretty well known) but I do not find that as elegant. However if you are emphasizing max flow/min cut as opposed to the linear programming structure, then you might want to do that one.

-
 Do you have a reference for the max flow/min cut proof? – Darsh Ranjan Feb 18 2010 at 17:21 Not off the top of my head, you can take any of the proofs of Birkhoff-von Neumann by Hall's Theorem (for example here: planetmath.org/…) smash that together with a proof of Hall's Theorem by max flow/min cut (cs.umass.edu/~barring/cs611/lecture/11.pdf). I did see a max flow/min cut version of BvN on the internet a while back. Surprisingly, I haven't previously seen the versions I sketched in this thread. The vertex condition approach seems the most direct possible way to go. The dual version is microscopically less obvious. – Andrew Mullhaupt Feb 18 2010 at 21:41

Not sure how non-obvious this is, but graph cuts and max-flow have been extensively used in computer vision for problems such as image segmentation or finding stereo correspondences. Here's a wiki page and a paper (pdf).

-

Take a look in the book:

Network Flows: Theory, Algorithms, and Applications

by: R. Ahuja, T. Magnanti, and J. Orlin

Prentice-Hall, 1993.

There you will find many examples of the kind that you are asking for.

-