Approximation Algorithms
Offered By: Ryan O'Donnell via YouTube
Course Description
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
算法设计与分析 Design and Analysis of AlgorithmsPeking University via Coursera Introdução à Ciência da Computação com Python Parte 2
Universidade de São Paulo via Coursera Learn Advanced Data Structures with Python: Trees
Codecademy Automata Theory
Stanford University via edX Computation in Complex Systems (Spring 2023)
Santa Fe Institute via Complexity Explorer