Algorithms for NP-Hard Problems (Section 21.2: Color Coding) [Part 2 of 2]
Tim Roughgarden Lectures · 15:48
Color coding finds a minimum-cost \(k\)-path by randomly coloring vertices with \(k\) colors so some optimal path becomes panchromatic (all distinct colors) with probability \(k!/k^k \approx \sqrt{2\pi k}/e^k\), then...