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

Start learning Write review
Coursera Ad

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

Learn More → DataCamp Ad

AI Engineer - Learn how to integrate AI into software applications

Learn More →

Overview

Google, IBM & Meta Certificates – 40% Off
One Coursera Plus subscription covers most Professional Certificates on Coursera.
Unlock All Certificates
This course introduces approximation algorithms for NP-complete optimization problems. It analyzes Vertex Cover, k-Coverage, and TSP through approximation guarantees, counterexamples, and hardness results.

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

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.