Explore approximation algorithms in this comprehensive lecture. Delve into the beautiful theory of algorithmic complexity and learn about various approximation techniques. Discover Gavril's Approximation Algorithm and its application to the Max-Cut problem. Examine the Greedy Vertex Cover algorithm, analyzing its performance and limitations through examples. Investigate the k-Coverage problem and its real-world applications, such as the "Pokémon-Coverage" problem. Study the Traveling Salesperson Problem (TSP) and learn about the MST Heuristic as a basic approximation algorithm. Gain insights into the theoretical foundations and practical applications of approximation algorithms in computer science and optimization.
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
Related Courses
-
Great Ideas in Theoretical Computer Science - Approximation Algorithms
-
Approximation Algorithms and Linear Programming
5.0 -
Approximation Algorithms
-
Data Structures & Algorithms IV: Pattern Matching, Dijkstra’s, MST, and Dynamic Programming Algorithms
5.0 -
Approximation Algorithms Part I
5.0 -
Matthias Mnich - Time- and Space-Optimal Algorithms for the Many-Visits TSP
