Computer Science 690AA - ApprxAlgorithms/ComboOpt

Many important problems that arise in practical applications of discrete optimization are NP-hard. This implies no polynomial time algorithms exist for these problems unless P==NP. The field of approximation algorithms has developed to tackle this difficulty by designing polynomial time algorithms to solve otherwise intractable problems near-optimally. Approximation algorithms provide rigorous guarantees on approximation factors indicating how far the solution can be in the worst case. This paradigm has become a cornerstone in algorithm design, and this course aims to cover a comprehesive list of topics in this area at the graduate level. Towards the end of the course, we will also explore ``hardness of approximation'': study of the best approximation factor possible in polynomial time. A tentative list of topics include:

Techniques - Greedy algorithms, local search, dynamic programming, randomized methods, LP techniques, primal-dual method, lagrangian methods, semi-definite programming, metric method, hardness of approximation.
Problems - Set cover, Vertex cover, TSP and other planning problems, Scheduling and Generalized assignment problems, Facility Location, Steiner tree and other network design problems, Sparsest cut, multicut and other graph partitioning problems, MaxSat, Graph coloring, Approximate counting, Algorithms on sequences etc.

Open to Graduate Computer Science students only. STUDENTS NEEDING SPECIAL PERMISSION MUST REQUEST OVERRIDES VIA THE ON-LINE FORM: https://www.cs.umass.edu/overrides.