From Set Cover to Shortest Superstring
The shortest superstring problem can be solved using greedy set cover approximation, loosing an extra factor 2 on the way.
00:00 Shortest Superstring Problem
03:32 Reduction to Set Cover
06:11 OPT(SSS) \leq OPT(SC)
08:07 OPT(Sc) \leq 2*OPT(SSS)
14:20 Algorithm
15:49 Final Remarks
Acknowledgments: Slides for approximation algorithms are mostly due to colleagues in Würzburg, in particular Joachim Spoerhase and Alexander Wolff. Thanks!