3 ms·
Karger's randomized contraction algorithm for finding a min-cut. It's a common algorithm to introduce students into the world of randomized algorithms. Also a
by chaoxu 8y ago
Karger's randomized contraction algorithm for finding a min-cut. It's a common algorithm to introduce students into the world of randomized algorithms.
Also a shameless plug. My friend and I came up with this pseudo-polynomial time algorithm for subset sum that can be taught in a single session. It is faster than the standard dynamic programming algorithm.
https://arxiv.org/abs/1807.08248 https://arxiv.org/abs/1807.08248
- GautamGoel 8y agoI actually read some of this paper! I liked your FFT trick.
- chaoxu 8y agoThanks! Do you use that algorithm for anything in your research?
- GautamGoel 8y agoNot directly. I briefly thought that a certain computational number theory problem might involve subset sums, but alas, it turned out to be the wrong approach.