Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Approximation Algorithms

Ryan O'Donnell via YouTube

Overview

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.

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

Reviews

Start your review of Approximation Algorithms

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.