Lecture 1 (Aug 25)
We reviewed some basic concepts regarding notions of efficient and inefficient computation, as well as basic concepts related to multiplicative/additive approximation for minimization and maximization problems. (Slides)
Lecture 2 (Aug 27)
As a first example, we saw a 2-factor approximation algorithm for the Vertex Cover problem. Note that this 2-factor approximation guarantee is tight (see this paper by Khot and Regev). The analysis of the algorithm proceeds by connecting vertex covers with maximum/maximal matchings. (Slides)
Lecture 3 (Sep 1)
We discussed the (ln(n) + 1)-factor greedy algorithm for the classical Set Cover problem; Set Cover type problems have been studied extensively in the literature, and you can read more about recent advances on such problems here. The (ln(n) + 1)-approximation is nearly tight; the result that (1 - o(1)) ln(n) approximation for Set Cover is NP-hard was developed over several works and the state-of-the-art can be found here. (Slides)