Overview
Syllabus
Intro
INVENTS BEAUTIFUL THEORY OF ALGORITHMIC COMPLEXITY
Don't Give Up
Gavril's Approximation Algorithm
Max-Cut
A technicality: Optimization vs. Decision
Today: A case study of
GreedyVC example
Greedyvc analysis
A bad graph for GreedyVc
A worse graph for GreedyVc
Even worse graph for GreedyVc
Greed is Bad (for Vertex-Cover)
Gavril to the rescue
Theorem: GavrilVC is a 2-approximation for Vertex-Cover.
"k-Coverage" problem
"Pokémon-Coverage" problem
Example with k=3
Greed is Pretty Good (for k-Coverage)
TSP (Traveling Salesperson Problem)
TSP example
Textbooks
"Popular" books
Museum exhibits
Movies
Basic Approximation Algorithm: The MST Heuristic
MST Heuristic example
MST Heuristic Theorem: MST Heuristic is factor-2 approximation.
Can we do better?
Taught by
Ryan O'Donnell