7 ms·
Runtime improvement for Minimum Cut algorithm first time in 25 years (2019)
- klyrs 6y ago[2019]
- dang 6y agoAdded. Thanks!
- vsskanth 6y agoWhat is it used for
- j16sdiz 6y agoIt is used for calculate the maximum flow of a flow network. https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Application https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Appli...
- PartiallyTyped 6y agoThe max flow is the prime to the min-cut. But you don't use min-cut to find the max flow.
- vmladenov 6y agoI don’t understand the distinction you’re drawing. Can you explain? Max flow and min cut are entirely dual. Which one you use is more a matter of convenience
- PartiallyTyped 6y agoWhat I meant was that if you wish to find the maximum flow, you'd use push-relabel or another max-flow algorithm instead of finding the min-cut first and then building the max-flow solution from there.
- stiar 6y agoWell if you have designated source (s) and sink (t) in a directed network, then yes, finding max s-t flow and min s-t cut are dual problems. Here the paper seems to be dealing with undirected graphs and all cuts in them, not necessarily between a given pair of vertices, so it is slightly different.
- krastanov 6y agoThis is a bit like asking what is matrix diaginalization used for. The applications are much too numerous in many different fields of science and engineering. "Graph partition" problems generally search for ways to separate a graph into subgraphs such that some measure is optimized. E.g. resilience of network connections, immunizations, some error correction algorithms, optimizing flow of stuff through nodes, logistics. This list probably barely scratches the surface. Edit: my comment sounds a bit rude on second read. My apologies, it is the limitations of this medium.
- vsskanth 6y agoThanks. I wasnt being snarky. I really didn't know what such algorithms are used for and the paper didn't mention examples either.
- anticensor 6y agoThis problem is assumed to be common knowledge among graph theory specialists.
- Fordec 6y agoEveryone on Hacker News is not assumed to be graph theory specialists.
- strictfp 6y agoThat's assumed common knowledge for non-graph theory specialists.
- bosswipe 6y agoI would say it's common knowledge for anyone with a CS degree.
- aliahsan07 6y agoits a bit advanced. Many university curriculums just skim through max flow min cut algorithms in a week or two as part of the algorithms class.
- jojobas 6y agoBan half of Twitter accounts so that as little people as possible notice.
- dang 6y ago"Eschew flamebait. Don't introduce flamewar topics unless you have something genuinely new to say. Avoid unrelated controversies and generic tangents." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- Geminidog 6y agoIt's used for passing the interview at a FAANG.
- glglwty 6y agoGraph cut is useful in computer vision.
- petters 6y agoStill used extensively for background-forground segmentation in e.g. Photoshop, I am guessing. Research these days mostly focuses on deep learning though.
- xiphias2 6y agoIt is a fundamental graph problem with many applications in different fields, such as network reliability, where assuming equal failure probability edges, the smallest edge cut in the network has the highest chance to disconnect the network; in VLSI design, where the minimum cut can be used to minimize the number of connections between microprocessor blocks; and as a subproblem in branch-and-cut algorithms for the Traveling Salesman Problem (TSP) and other combinatorial problems. (Copy paste from viecut github repo)
- vsskanth 6y agoThanks.
- optimalsolver 6y agoI remember a CS prof saying he moved from hardware to software because the speedups possible in algorithm design dwarf anything you can achieve by improving the bare metal.
- vlovich123 6y agoI don’t think that’s actually the case. HW is just harder to implement in a cost effective way as the ways you make it fast for a given problem may not lend itself to solving other problems and HW is insanely expensive to build stemming from how long and labor intensive it is (design, validation and tape out + cost of fixing bugs)
- klodolph 6y agoBut that’s a selective way to think about cost, isn’t it? If you ignore NRE, almost anything is cheaper in hardware. But you can't ignore NRE.
- vlovich123 6y agoThe same algorithm in SW is drastically cheaper to implement even before you get to anything else you need for Hw. Everything else is gravy on top.
- thwero234234 6y agoIt's a nice sentiment, but it's not always true. Case in point: none of the algorithmic improvements to matrix-multiplication has had any real effect on deep-learning etc (except Winograd convolution).
- andrewem 6y agoThere’s this example of your point, which claims that “Compiler Advances Double Computing Power Every 18 Years” http://proebsting.cs.arizona.edu/law.html http://proebsting.cs.arizona.edu/law.html
- 6y ago
- saagarjha 6y agoQuestion: is this algorithm practical to implement?
- 0x23 6y agoOn that note, here is the currently fastest implementation for the problem https://arxiv.org/abs/1808.05458 https://arxiv.org/abs/1808.05458 and here on github https://github.com/viecut/viecut https://github.com/viecut/viecut
- londons_explore 6y agoCan someone give a more concrete example of this problem? I read the wiki page[1], and I'm left with the impression that for almost all cases, the minimum cut will be to pick a node and seperate it from the rest of the nodes. It doesn't sound like a very computationally difficult or useful algorithm if one of the two parts of the results usually consists of a single node... [1]: https://en.wikipedia.org/wiki/Minimum_cut https://en.wikipedia.org/wiki/Minimum_cut
- interpol_p 6y agoI used the minimum cut algorithm to implement a texture synthesis algorithm [1]. When the images to merge are represented as a graph of connected pixels, you can use the minimum cut algorithm to try to find the lowest energy path that cuts across both images This minimises the differences between the images along the seam so they appear to blend together [1] https://www.cc.gatech.edu/~turk/my_papers/graph_cuts.pdf https://www.cc.gatech.edu/~turk/my_papers/graph_cuts.pdf
- ivanbakel 6y agoWikipedia has a nice diagram on another page[0] - in a weighted graph where all nodes have enough connections, separating just a single node is likely to cost more than finding some cheap partition between two groups. [0] https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm#/media/File:Stoer_wagner-example-min-cut.gif https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm...
- est31 6y agoThe classical example used to introduce this problem in lectures is the one about the soviet rail network: https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-ma... Legend has it both Soviets and Americans studied it, both identifying the bottleneck for opposite reasons: Americans wanted to disrupt as much as possible by destroying as few rails as possible while Soviets wanted to extend the network's ability to transport goods with building the fewest connections... Both problems are equivalent, known as the max flow min cut theorem.
- xdavidliu 6y ago
- chaoxu 6y agoThere are a few misconceptions that some other commenters are already making. This min-cut is different from the max-flow min-cut theorem's min-cut. This is what referred to as global min-cut, which does not fix the terminals. In max-flow min-cut theorem, it is about disconnecting two fixed vertices s and t. In the global min-cut, it is about disconnecting two arbitrary vertices. Source: thesis was on hypergraph min-cut
- est31 6y agoSo the question is to find an arbitrary set of edges that partition the graph? In a K_n with equally weighted edges this problem seems easy: just take a random vertex and remove the edges connecting it to the neighbourhood. Any attempt at removing more vertices would yield in having to cut more edges, so the strategy removes the least amount of edges while partitioning the graph. In a tree with equally weighted edges, this problem seems easy too: just remove a leaf. Every tree has leaves. I can't think about graphs "between" the two creating a property that makes the the "I just take the vertex with the fewest adjacencies and remove it" strategy moot. Is it trivial with equally weighted edges? Is the problem only interesting when edges have differing weights?