most recent 30 from http://mathoverflow.net 2013-06-18T07:19:51Z http://mathoverflow.net/feeds/question/15614 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming Wilson 2010-02-17T19:26:55Z 2010-07-12T14:23:22Z

<p>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.</p> <p>Any ideas?</p>

http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming/15619#15619 Joseph Malkevitch 2010-02-17T19:47:36Z 2010-02-17T19:47:36Z

<p>Take a look in the book:</p> <p>Network Flows: Theory, Algorithms, and Applications</p> <p>by: R. Ahuja, T. Magnanti, and J. Orlin</p> <p>Prentice-Hall, 1993.</p> <p>There you will find many examples of the kind that you are asking for.</p>

http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming/15626#15626 sheldon-cooper 2010-02-17T20:38:06Z 2010-02-17T20:38:06Z

<p>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 <a href="http://en.wikipedia.org/wiki/Graph%5Fcuts%5Fin%5Fcomputer%5Fvision" rel="nofollow">wiki page</a> and a <a href="http://www.cs.cornell.edu/~rdz/Papers/BVZ-pami01-final.pdf" rel="nofollow">paper (pdf)</a>.</p>

http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming/15638#15638 Tony Huynh 2010-02-17T22:32:12Z 2010-02-17T22:32:12Z

<p>Determining whether a sports team has been mathematically eliminated from qualifying for the playoffs is a cute application of max-flow min-cut: </p> <p><a href="http://www.cs.princeton.edu/courses/archive/spr03/cs226/assignments/baseball.html" rel="nofollow">http://www.cs.princeton.edu/courses/archive/spr03/cs226/assignments/baseball.html</a></p>

http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming/15640#15640 Andrew Mullhaupt 2010-02-17T22:50:48Z 2010-02-17T22:50:48Z

<p>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".</p> <p>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.</p> <p>I came up with this myself so don't know of an actual reference, but it should not be that novel.</p> <p>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.</p>

http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming/15678#15678 Suresh Venkat 2010-02-18T07:45:27Z 2010-02-18T07:45:27Z

<p>The <a href="http://www.aw-bc.com/info/kleinberg/" rel="nofollow">algorithms book by Kleinberg and Tardos</a> 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. </p> <p>The examples work, in that students tend to have 'aha' moments (or so they tell me). </p>

http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming/31556#31556 falagar 2010-07-12T14:23:22Z 2010-07-12T14:23:22Z

<p>Another interesting application of LP is finding Nash equilibrium for a two player zero-sum game.</p> <p><a href="http://en.wikipedia.org/wiki/Zero-sum_game#Solving" rel="nofollow">http://en.wikipedia.org/wiki/Zero-sum_game#Solving</a></p>