Runtime improvement for Minimum Cut algorithm first time in 25 years (2019)
arxiv.org
arxiv.org
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
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?
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...
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
[0] https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm...
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.
You're assuming that nodes have 1 or 2 edges coming out of them. If every node has up to (# nodes)-1 edges incident on it, then it's non-obvious which of the 2^(# node) subsets gives the min cut.
It's definitely not justified to only consider the subsets with 1 nodes: what if you have 10 nodes: 5 blue and 5 yellow, and the blue ones are all connected to each other with extremely heavy edges, and similar for the yellow nodes, and there is one very light edge between the two regions? Then in this case, the min cut would be to separate blue from yellow (i.e. cut off a 5-node subset), _not_ 1 node.
The general case of arbitrary nodes and edges will be somewhere in between what I have described and what you're thinking of, so a general algorithm that works for all cases is definitely not as trivial as just trying out every 1-node subset.
> Take two copies of K_4. Connect them with a single edge. The minimum cut is the single connector edge while your proposed strategy would delete the three edges out of one of the vertices not incident to the connector edge.
Edit: my comment sounds a bit rude on second read. My apologies, it is the limitations of this medium.
If you have a bunch of chat users and a bunch of chat servers, and you want to figure out how to assign users to servers in a way that minimizes the number of messages going between your chat servers, then you're solving a min cut problem on a graph where users are nodes, edges are communications, and edge weights are communications volumes. Any links that you cut in order to partition the graph end up being cross-server traffic.
Research these days mostly focuses on deep learning though.
(Copy paste from viecut github repo)
Case in point: none of the algorithmic improvements to matrix-multiplication has had any real effect on deep-learning etc (except Winograd convolution).
Is implementing an algorithm in hardware ever done before all of the obvious software optimizations have been exhausted? If not, how would you know you're implementing the best known version of the algorithm?
It seems to me that hardware is a route to improvement, but only after all of the software improvements have been done. If you want to spand your career making computers do stuff faster there'll always be more work to do in software, simply because if you can make something fast enough there you don't need to implement it in hardware.
That said, when you implement specialized algorithms in hardware, it's likely because it's good enough for the task it's designed for.
Then again, there is this crypto-mining boom, where custom ASICs and GPUs literally pay for themselves. There, the associated algorithms were specified to be slow, and no improvements on them can be reasonably expected unless quantum computing takes off for real and opens new venues.
The advantage of speeding up hardware is that it scales to most present and future programs. Though it's a bit of an economic activity. As the hardware gets faster, software developers de-prioritize algorithmic speed in favour of faster product development or research.