The field of approximation algorithms has developed in response to the difficulty in solving a good many optimization problems exactly. In the case of NP-hard problems, we sacrifice optimality in the favor of efficient heuristics that give nearly-optimal (approximate) solutions, and aim for provable guarantees on the performance of these algorithms. This course will present some general techniques (such as convex programming-based approaches, randomness and metric methods) that underly these algorithms. The following is a selection of the techniques and problems that we will cover:
Techniques: greedy algos, local search, randomized methods, LP techniques, primal-dual method, lagrangean methods, semi-definite programming, metric methods, inapproximability.
Problems: Set cover. Vertex cover. TSP & other planning problems. Scheduling. Facility location. Steiner tree and other network design problems. Sparsest cut, multicut and other partitioning problems. MaxSAT. Generalized assignment problems. Graph coloring. Approximate counting.
- Online optimization algorithms [PDF] by Dave Andrzejewski
- Bounds on alphabet size and rate for network coding [PDF] by Siddharth Barman
- Network coding [PDF] by Matt Elder
- Stochastic optimization [PDF] by Chi Man Li