Completed
Theorem: GavrilVC is a 2-approximation for Vertex-Cover.
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Great Ideas in Theoretical Computer Science - Approximation Algorithms
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 given a Boolean formula F. is it satisfiable?
- 3 INVENTS BEAUTIFUL THEORY OF ALGORITHMIC COMPLEXITY
- 4 Don't Give Up
- 5 Gavril's Approximation Algorithm
- 6 Max-Cut
- 7 A technicality: Optimization vs. Decision
- 8 Today: A case study of
- 9 A possible Vertex-Cover algorithm
- 10 GreedyVC example
- 11 GreedyVc analysis
- 12 A bad graph for GreedyVc
- 13 A worse graph for GreedyVc
- 14 Greed is Bad (for Vertex-Cover)
- 15 Gavril to the rescue
- 16 GavrilVC example
- 17 Theorem: GavrilVC is a 2-approximation for Vertex-Cover.
- 18 "k-Coverage" problem
- 19 "Pokémon-Coverage" problem
- 20 Example with k=3
- 21 Greed is Pretty Good (for k-Coverage)
- 22 TSP (Traveling Salesperson Problem)
- 23 TSP example
- 24 Textbooks
- 25 Museum exhibits
