Approximation Algorithms

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!

Grab it

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?