Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

6 Answers 6

up vote 6 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
Do you have a reference for the max flow/min cut proof? –  Darsh Ranjan Feb 18 '10 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/?op=getobj&from=objects&id=3611) 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 '10 at 21:41

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).

share|improve this answer

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).

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.