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)
Lecture 4 (Sep 3)
We saw the seminal (1 - 1/e)-approximation algorithm for Constrained Submodular Maximization. As discussed, beyond max-coverage, submodular maximization also expresses several other problems of practical interest such as influence maximization and feature selection (see here and here). Also, the greedy algorithm discussed in class can be thought of as the discrete analogue of maximizing a concave function (see here for a discussion). Finally, the (1 - 1/e)-approximation was shown to be tight in Feige's paper. (Slides)
Lectures 5,6,7 (Sep 10,15,17)
We explored the symmetric and asymmetric variants of the Traveling Salesman Problem. For the symmetric setting, we saw a 2-factor approximation, and the improved 1.5-factor approximation as well, and the log(n) approximation for the asymmetric setting. The recent improvements for the symmetric and asymmetric variants can be found here and here respectively. (Slides 5,6,7)