This course on Approximation Algorithms in Theoretical Computer Science aims to teach students the following:
- Understanding the concept of approximation algorithms and their applications in solving complex computational problems.
- Learning about Gavril's Approximation Algorithm, Max-Cut, Vertex-Cover algorithms, and their analyses.
- Exploring the difference between optimization and decision problems in the context of algorithmic complexity.
- Studying real-world case studies such as the "k-Coverage" problem and the Traveling Salesperson Problem (TSP).
The course teaches individual skills such as algorithm analysis, problem-solving, and understanding the trade-offs between greedy algorithms and optimal solutions. The teaching method involves theoretical lectures, algorithm demonstrations, and case study discussions. This course is intended for students and professionals interested in theoretical computer science, algorithm design, and computational problem-solving.
Great Ideas in Theoretical Computer Science - Approximation Algorithms
Overview
Syllabus
Intro
given a Boolean formula F. is it satisfiable?
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
A possible Vertex-Cover algorithm
GreedyVC example
GreedyVc analysis
A bad graph for GreedyVc
A worse graph for GreedyVc
Greed is Bad (for Vertex-Cover)
Gavril to the rescue
GavrilVC example
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
Museum exhibits
Taught by
Ryan O'Donnell
