MIT

Lecture 11: Inapproximability Examples

Data Science, Analytics & Computer TechnologyAlgorithms and Data StructuresComputer ScienceScience & MathMathematicsEngineering

Om kurset

Description: In this lecture, Professor Demaine explains L-reductions to prove various problems APX-complete, introduces a characterization theorem for approximability, and mentions the approximation spectrum. Instructor: Erik Demaine A video player with synced slides and lecture notes is available.