Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
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 4 '13 at 6: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 4 '13 at 6: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 4 '13 at 6: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 4 '13 at 8:20
4  
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. –  JɛffE Feb 4 '13 at 14:40
show 4 more comments

2 Answers

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.

share|improve this answer
    
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 4:26
add comment

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

share|improve this answer
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 4 '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 4 '13 at 22:07
3  
@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 5 '13 at 2: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 5 '13 at 3:58
2  
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 5 '13 at 18:09
show 2 more comments

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.