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

YouTube

Great Ideas in Theoretical Computer Science - Approximation Algorithms

Ryan O'Donnell via YouTube

Start learning Write review
Coursera Ad

AI, Data Science & Cloud Certificates from Google, IBM & Meta

Learn More → Babbel Ad

You’re only 3 weeks away from a new language

Learn More →

Overview

Google, IBM & Meta Certificates – 40% Off
One Coursera Plus subscription covers most Professional Certificates on Coursera.
Unlock All Certificates
This lecture examines approximation algorithms through greedy methods and graph optimization problems such as Vertex Cover, k-Coverage, Max-Cut, and TSP. It includes analysis of poor greedy cases and a proof that Gavril's algorithm is a 2-approximation for Vertex Cover.

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

Reviews

Start your review of Great Ideas in Theoretical Computer Science - Approximation Algorithms

Start learning

Never Stop Learning.

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

Sign up for free
Someone learning on their laptop while sitting on the floor.