32
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ 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... $\endgroup$
    – vzn
    Commented Feb 4, 2013 at 6:36
  • 3
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Feb 4, 2013 at 6:45
  • 3
    $\begingroup$ @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. $\endgroup$
    – Rob Lachlan
    Commented Feb 4, 2013 at 8:20
  • 5
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Feb 4, 2013 at 14:40
  • 2
    $\begingroup$ Here's the code from Experimental study of minimum cut algorithms. $\endgroup$
    – Austin Buchanan
    Commented Apr 20, 2013 at 18:36

3 Answers 3

Reset to default
23
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – vzn
    Commented Mar 19, 2013 at 4:26
8
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ +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. $\endgroup$
    – Rob Lachlan
    Commented Feb 4, 2013 at 21:13
  • 3
    $\begingroup$ 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. $\endgroup$
    – Juho
    Commented Feb 4, 2013 at 22:07
  • 5
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Commented Feb 5, 2013 at 2:58
  • 2
    $\begingroup$ @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. $\endgroup$
    – Rob Lachlan
    Commented Feb 5, 2013 at 3:58
  • 3
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Feb 5, 2013 at 18:09
5
$\begingroup$

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/

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.