Completed
Theorem: GavrilVC is a 2-approximation for Vertex-Cover.
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Approximation Algorithms
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 INVENTS BEAUTIFUL THEORY OF ALGORITHMIC COMPLEXITY
- 3 Don't Give Up
- 4 Gavril's Approximation Algorithm
- 5 Max-Cut
- 6 A technicality: Optimization vs. Decision
- 7 Today: A case study of
- 8 GreedyVC example
- 9 Greedyvc analysis
- 10 A bad graph for GreedyVc
- 11 A worse graph for GreedyVc
- 12 Even worse graph for GreedyVc
- 13 Greed is Bad (for Vertex-Cover)
- 14 Gavril to the rescue
- 15 Theorem: GavrilVC is a 2-approximation for Vertex-Cover.
- 16 "k-Coverage" problem
- 17 "Pokémon-Coverage" problem
- 18 Example with k=3
- 19 Greed is Pretty Good (for k-Coverage)
- 20 TSP (Traveling Salesperson Problem)
- 21 TSP example
- 22 Textbooks
- 23 "Popular" books
- 24 Museum exhibits
- 25 Movies
- 26 Basic Approximation Algorithm: The MST Heuristic
- 27 MST Heuristic example
- 28 MST Heuristic Theorem: MST Heuristic is factor-2 approximation.
- 29 Can we do better?
