32

For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an algorithm that runs in O(VE).

On the other hand, the algorithms I most commonly see implemented are (I don't claim to have done an exhaustive search; this is just from casual observation):

  • Edmonds-Karp: $O(VE^2)$,
  • Push-relabel: $O(V^2 E)$ or $O(V^3)$ using FIFO vertex selection,
  • Dinic's Algorithm: $O(V^2 E)$.

Are the algorithms with better asymptotic running time just not practical for the problem sizes in the real world? Also, I see "Dynamic Trees" are involved in quite a few algorithms; are these ever used in practice?

Note: this question was originally asked on stack overflow, here, but I was told it would be a better fit here.

EDIT: I asked a related question on cs.stackexchange, specifically about the algorithms that use dynamic trees (aka link-cut trees), which may be of interest for people following this question.

Community
  • 1
Rob Lachlan
  • 421
  • 4
  • 5
  • 1
    speaking in a general sense, whether an algorithm is "practical" vs whether it is "implemented" are a bit different. ideally authors would release implementations of their own algorithms in which case it would usually be "practical" to use them. unf this is often more the exception in TCS literature. but its often not "practical" to "implement" other authors algorithms only given descriptions in papers written in pseudocode, which are sometimes significantly or highly complex... successful implementation includes good testing for correctness, a sometimes daunting process... – vzn Feb 04 '13 at 06:36
  • 1
    @vzn I would expect that some big tech companies would be willing to put in the effort to see if these algorithms are worth the improvement, no? (I'm not sure how often max-flow problems come up in such places...I'd assume somewhat often.) – usul Feb 04 '13 at 06:39
  • 3
    Andrew Goldberg used to have a very nice code base for different variants of max flow based on his push relabel work. I've used the code in the past, and it was very clean. Unfortunately, the site appears to be defunct. – Suresh Venkat Feb 04 '13 at 06:45
  • 3
    @vzn I'm interested in whether the algorithms lend themselves to practical implementation at all. There are algorithms that don't, and some people have taken to calling these "galactic algorithms", because they have excellent asymptotic behaviour but so much overhead that there's currently no practical gain to implementing them. (Lower order terms matter, after all.) Matrix multiplication is the best example I can think of, where the asymptotically best solutions never see practical use. I'm curious as to whether Max flow is a similar situation. – Rob Lachlan Feb 04 '13 at 08:20
  • 5
    whether an algorithm is "practical" vs whether it is "implemented" are a bit different. — That is correct. An algorithm can be implemented without being practical, but not vice versa. – Jeffε Feb 04 '13 at 14:40
  • looking at the paper, it does seem to verge on "not likely to be actually implemented due to a high threshhold of logical complexity" see eg Powerful Algorithms too complex to implement. some commentary/comments on the orlin result by lance fortnow et al on his blog. the lower bound utilizes also the King, Rao and Tarjan algorithm so both algorithms would have to be implemented to get the theoretical optimum. – vzn Feb 04 '13 at 18:45
  • as for companies implementing new max flow algorithms, that is possible, but then why release them to the public domain & other parties when they invested the time? sometimes better for them to retain the competitive advantage. this is heightened in that, in fact, have heard max flow is useful in realtime trading applications where secrecy is common! – vzn Feb 04 '13 at 18:59
  • @vzn I am not very familiar with article licenses, but shouldn't they reference the author in the software and if possible, notify him as well. I am thinking a copyleft license would be appropriate here. Perhaps this would make a good question. – chazisop Feb 05 '13 at 12:39
  • 2
    Here's the code from Experimental study of minimum cut algorithms. – Austin Buchanan Apr 20 '13 at 18:36
  • seems relevant: http://cacm.acm.org/magazines/2014/8/177011-efficient-maximum-flow-algorithms/fulltext – Radu GRIGore Sep 02 '14 at 04:32

3 Answers3

23

I am one of the authors of the paper linked above.

Just want to mention that we used ``state-of-the-art'' to mean algorithms (with publicly available implementations) that perform well on max-flow instances arising in computer vision.

I would also like to add that within that narrow (yet practical) context, often the algorithms that perform well are the ones with poor theoretical guarantees. For instance, ref [5] from our paper (Boykov-Kolmogorov algorithm) is widely used in the computer vision community, but does not have a strongly polytime runtime bound.

Finally, in case anyone is interested, the data from our experiments is available here: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

The code will also soon be available too.

Dhruv Batra
  • 231
  • 1
  • 2
  • very neat that you joined the group! welcome! one question about the paper [since 1st finding it]. it would be very interesting to hear more about the process of selection of algorithms used in the paper— it didnt seem to fully elaborate on that. maybe you could share some "behind-the-scenes" background notes somewhere [eg web page?] about which algorithms were selected, which were omitted, why, what challenges there were in obtaining/running implementations, what you think of the more exotic algorithms such as Orlins recent one & their prospects for eventual implementation, etcetera! – vzn Mar 19 '13 at 04:26
8

there are several ways to answer this question but not necessarily a consensus answer. generally algorithms that have been implemented and released for public distribution are "practical". however, some algorithms that have been devised but not yet implemented may be practical but "the jury is out" on them so to speak.**

a good strategy for practical purposes is to look for a survey. also for those interested in practical algorithms, benchmarks against real world data can be an excellent guideline as to their expected "real world" behavior.

a benchmarking survey can be sufficient but will err on the side of viable algorithms. this is a recent, thorough empirical analysis of 14 "state-of-the-art" max flow algorithms benchmarked empirically versus vision processing instances, where max flow has many applications. "state of the art" is taken to refer to "implemented" algorithms.

[1] MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems by Verma and Batra, 2012

** some theoretical algorithms are in a category increasingly in the TCS community being informally referred to as "galactic" but unfortunately, TCS authors do not currently forthrightly self-label their algorithms in this category, and there is no published or generally accepted criteria for "galactic" algorithms, although there is reference in blogs.

practicality in this sense is possibly a new emerging dimension for theoretical study. ideally there would be a survey of max flow algorithms specifically on this "practical" axis/criteria, but likely that does not exist as of writing. its a more recently recognized/acknowledged concept in TCS that hasnt been thoroughly formalized yet (unlike eg the widespread acceptance of P algorithms as "efficient").

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 3
    +1. I'm not sure why this was downvoted; I'm reading the paper that you linked to, and it has been very helpful in looking at what the practical approaches are, at least in that problem domain. – Rob Lachlan Feb 04 '13 at 21:13
  • 3
    Robert Sedgewick said in a fairly recent talk that the algorithm designer who does not run experiments risks becoming lost in abstraction. The talk is about finding paths in graphs, and is somewhat related to maxflow too. It doesn't answer the question, but might be interesting to someone. – Juho Feb 04 '13 at 22:07
  • 5
    @Rob, the only relevant part in this answer is a link to the paper and there isn't much in the answer explaining why that paper is linked at all. I would guess that the OP found the link by Google and hasn't read it. The rest of the answer is some general remarks and commentary stating OP's personal perspective on issues that he is not an expert on and not really relevant here. Answers are not blog posts. A link to a relevant paper might be good as a comment but it doesn't make an answer. This is a bad answer if it is one. That is why I have down voted it. – Kaveh Feb 05 '13 at 02:58
  • 2
    @Kaveh fair enough. I found the paper to be a useful indicator of what people consider to be practically useful algorithms. I agree that much is left unanswered. – Rob Lachlan Feb 05 '13 at 03:58
  • cannot write a treatise on the subj. skimmed paper, its highly relevant. esp given that authors attempt to test all recent state-of-the-art algorithms & hard instances in one field/domain may tend to coincide with hard ones in another. ie performance results can generally/often carry between domains. empirical testing is highly relevant with basic disclaimers. TCS ivory tower crowd devalues empirical approaches & can get lost in theory as sedgewick points out. even Fortnow & Lipton, premiere TCS authorities, while crediting advances, still question "galactic" algorithms. the paper is science – vzn Feb 05 '13 at 15:42
  • 3
    I don't understand the downvotes either. There's no reason to believe that the poster did NOT read the linked article, and it does appear to be relevant. I can see the desire not to upvote, but not a downvote. – Suresh Venkat Feb 05 '13 at 18:09
  • 2
    @Suresh, my down-vote was not for that reason. As I explained above I see this as a one-line link answer which AFAIK is not considered a good answer (plus some general commentary expressing personal perspective which I think belong to a blog post and not here). I would take back my down-vote if the answer is edited, the general commentary is removed, and the relevance of this particular article to this particular question is explained. – Kaveh Feb 06 '13 at 04:57
5

You might be interested in Maximum Flows by Incremental Breadth-First Search by Goldberg, Hed, Kaplan, Tarjan, and Werneck

http://research.microsoft.com/pubs/150437/ibfs-proc.pdf http://www.cs.tau.ac.il/~sagihed/ibfs/

Christian Sommer
  • 761
  • 6
  • 7