Hardness of Approximation - Part 1

Hardness of Approximation - Part 1

Dive into the first part of a comprehensive tutorial on Hardness of Approximation presented by Ryan O'Donnell at the Metric 2011 workshop at IHP. Explore key concepts such as Max Cuts, Maximum Independent Set, Max K Cover, and the Unique Games Conjecture. Learn about basic decision problems, approximation algorithms, and the current state of affairs in the field. Gain insights into greedy algorithms, best-known approaches, and important approximability results. Engage with the material through questions and discussions, and familiarize yourself with essential notation and proofs in this 59-minute lecture, originally recorded by Nicolas Schabanel.