Completed
Even worse graph for GreedyVc
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?
