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?
 A: 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.
A: 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.
A: 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). 
A: 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
A: 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).
A: 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
