6
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ The book by Reichmeider, The Equivalence of Some Combinatorial Matching Theorems, has chapters on König's Theorem, Hall's Theorem, Dilworth's Theorem, Menger's Theorem, Max-Flow Min-Cut Theorem, and Some Linear Programming Considerations, so it's bound to have some interesting applications. $\endgroup$
    – Gerry Myerson
    Commented Sep 24, 2022 at 4:17

6 Answers 6

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have a reference for the max flow/min cut proof? $\endgroup$
    – Darsh Ranjan
    Commented Feb 18, 2010 at 17:21
  • $\begingroup$ 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. $\endgroup$
    – Andrew Mullhaupt
    Commented Feb 18, 2010 at 21:41
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .