Latest / Deep End Era. Engineering with Sankalp
Good Enough, Provably: Approximation Algorithms and Heuristics for NP-Hard Problems
A fictional airline's crew roster collapses after a sandstorm, and its lone optimisation engineer has six hours to rebuild it. Along the way: Christofides's unpublished 1976 report, Kirkpatrick's annealing of chips, an 85,900-city tour proved optimal, and a 2020 result that beat three halves by a margin smaller than 10 to the minus 36.
Chapters
00:00:00 Cold open: the roster that fell over
00:04:12 What does good enough mean?
00:05:48 Vertex cover: the matching trick
00:08:51 Set cover: greedy and its logarithm
00:12:17 The travelling salesman, guaranteed
00:17:37 More guarantees: scheduling…
The skinny
The skinny isn't ready yet — notes appear once the transcript is processed.