{"id":1212,"date":"2010-09-27T13:47:55","date_gmt":"2010-09-27T17:47:55","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1212"},"modified":"2010-09-27T13:47:55","modified_gmt":"2010-09-27T17:47:55","slug":"a-new-approach-to-maxflow","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/09\/27\/a-new-approach-to-maxflow\/","title":{"rendered":"A New Approach to MaxFlow?"},"content":{"rendered":"

The MIT public relations office is reporting a new result on the maximum flow problem<\/a>.\u00a0 It appears that work by Kelner<\/a>, Madry<\/a>, Christiano, Spielman<\/a> and Teng<\/a> (in some permutation:\u00a0 not surprisingly, the MIT release stresses the MIT authors) has reduced the complexity of maxflow to (V+E)^4\/3 (from (V+E)^3\/2.\u00a0 Details are pretty sketchy, but the approach seems to use matrix operations instead of the more combinatorial “push flow along this path (or edge)”.\u00a0 From the announcement:<\/p>\n

Traditionally, Kelner explains, algorithms for calculating max flow would consider one path through the graph at a time. If it had unused capacity, the algorithm would simply send more stuff over it and see what happened. Improvements in the algorithms\u2019 efficiency came from cleverer and cleverer ways of selecting the order in which the paths were explored.
\nBut Kelner, CSAIL grad student Aleksander Madry, math undergrad Paul Christiano, and Professors Daniel Spielman and Shanghua Teng of, respectively, Yale and USC, have taken a fundamentally new approach to the problem. They represent the graph as a matrix, which is math-speak for a big grid of numbers. Each node in the graph is assigned one row and one column of the matrix; the number where a row and a column intersect represents the amount of stuff that may be transferred between two nodes.<\/p>\n

In the branch of mathematics known as linear algebra, a row of a matrix can also be interpreted as a mathematical equation, and the tools of linear algebra enable the simultaneous solution of all the equations embodied by all of a matrix\u2019s rows. By repeatedly modifying the numbers in the matrix and re-solving the equations, the researchers effectively evaluate the whole graph at once.<\/p><\/blockquote>\n

I am a little hesitant here, since I can’t find the relevant paper.\u00a0 Worse, the presentation abstract talks about approximate maximum flow (see the September 28 entry at the MIT seminar listing<\/a>), which would then add in some extra terms for exact max flow.\u00a0\u00a0 So I welcome more information on the result.<\/p>\n

In any case, it is exciting to see a new approach to these sorts of problems.\u00a0 If past experience is any guide, if this approach is workable, we can expect to see an avalanche of papers applying the approach to all sorts of network flow problems: shortest path, min cost flow, generalized networks (with multipliers) and so on.\u00a0 A likely good place to start is this overview paper<\/a> by Spielman.<\/p>\n","protected":false},"excerpt":{"rendered":"

The MIT public relations office is reporting a new result on the maximum flow problem.\u00a0 It appears that work by Kelner, Madry, Christiano, Spielman and Teng (in some permutation:\u00a0 not surprisingly, the MIT release stresses the MIT authors) has reduced the complexity of maxflow to (V+E)^4\/3 (from (V+E)^3\/2.\u00a0 Details are pretty sketchy, but the approach … Continue reading “A New Approach to MaxFlow?”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[],"class_list":["post-1212","post","type-post","status-publish","format-standard","hentry","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1212","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1212"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1212\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}