Opening Complexity: Approximation Algorithms
Complexity: Approximation Algorithms
- Length
- 1 h 21 min
- Level
- Undergraduate
- Recorded
- MIT2016
Chapter 1 of 9: Before the lecture
Devadas proves a 2-approximation for vertex cover, a logarithmic bound for greedy set cover, and a PTAS for partition.
Approximation algorithms return solutions to NP-hard optimization problems that are provably within a fixed ratio of the optimum. Devadas opens session 19 of MIT 6.046J by defining the approximation ratio, the polynomial time approximation scheme (PTAS) and the fully polynomial scheme (FPTAS). Greedily picking disjoint edges then gives a 2-approximation for vertex cover. A pigeonhole and counting argument bounds greedy set cover by a logarithmic factor, a simpler route than the harmonic-number analysis in CLRS. The final part seeds exhaustive search with an optimal split of the largest elements, proving a bound for partition by case analysis on the last added element.
Approximation algorithms return solutions to NP-hard optimization problems that are provably within a fixed ratio of the optimum. Devadas opens session 19 of MIT 6.046J by defining the approximation ratio, the polynomial time approximation scheme (PTAS) and the fully polynomial scheme (FPTAS). Greedily picking disjoint edges then gives a 2-approximation for vertex cover. A pigeonhole and counting argument bounds greedy set cover by a logarithmic factor, a simpler route than the harmonic-number analysis in CLRS. The final part seeds exhaustive search with an optimal split of the largest elements, proving a bound for partition by case analysis on the last added element.

This lecture
Lecture 19 of 27 of Design and Analysis of Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in