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 these 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)
Lectures 9 + 10 (Sep 29 + Oct 1)
We saw a 6-factor approximation algorithm for the Facility Location problem, which is a classical problem in the clustering literature. Unlike Vertex Cover, where the rounding scheme was instance-oblivious, the rounding scheme discussed here uses up to second-order (i.e. 2 hop) neighborhood information. The current state-of-the-art for Facility Location is the following 1.488 approximation by Shi Li. (Slides)
Something to think about: can we improve the approximation guarantee by using rounding schemes that take into account more no. of neighborhood hops?
Lectures 11 + 12 (Oct 6 + Oct 8)
We discussed Basic Feasible Solutions for linear programs, and how they can be used to design iterated rounding schemes for rounding LPs. As an example, we saw a 2-factor approximation algorithm for the Tree Augmentation problem, which is a classic problem in network design. The use of geometry-based iterated rounding algorithms is a whole sub-area within approximation algorithms, and the following notes are a great place to know more. (BFS Slides, Tree Augmentation Slides).
Lecture 13 (Oct 13)
We introduced the randomized rounding technique and used to obtain a (1 - 1/e)-factor approximation algorithm for the Maximum Satisfiability problem. As we'll see in the upcoming lectures, randomness will play a crucial rule in the design of approximation algorithms for the most of the problems we will go on to discuss. In fact, for most of the purely combinatorial algorithms that we've seen before (e.g., Set Cover, Submodular Maximization), there's a LP + randomized rounding-based approach that can also yield the same optimal approximation guarantee. (Sildes)