الگوریتم های تقریبی
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.
The main reference for this course is the following book, but we will also include several recent papers in this area in our discussions. Please visit the reading list on the course webpage for extra reading material.
