Modern Approximation Algorithms
Matthew Johnson was educated at Lawrence, Columbia, and CUNY, and then was a postdoc different places before returning to CUNY as a faculty member. His research interests lie in algorithms.
The course is about approximation algorithms, and computer science is about algorithms. Students who liked the required algorithms class should take this class. It will be like that class, but more so. Students should possess a certain level of mathematical maturity.
In the 1970s it was discovered that in addition to decision problems like SAT and Partition, many, many important discrete optimization problems are (roughly speaking) NP-Complete, and so are unlikely to admit polynomial-time optimal algorithms. In such problems--e.g., traveling salesman, vertex cover, independent set, etc.--there is a large set of possible solutions and we search for a solution of minimum cost (or of maximum value). In the decades since, there has developed the theory of approximation algorithms. Such an algorithm typically guarantees that, given any possible problem instance, the solution found will be within some constant (multiplicative) factor c of the optimal, i.e., the solution cost is never greater than c*OPT, where c>1 (or the solution value is never less than c*OPT, where c<1) . It may be surprising that in the case of many optimization problems, it is possible to prove that our solutions will be close to OPT, even though we don't (and can't) know what OPT is. A set of fundamental techniques have emerged in recent decades for designing and analyzing the performance of such algorithms. In this course we will study these techniques and some of the most significant instances of their application.
Algorithms, and mathematical maturity.
Survey of major techniques used in the design and analysis of approximation
algorithms, i.e., algorithms providing guaranteed approximations for intractable
optimization problems, including:
These general techniques will be introduced by studying their application to various canonical optimization problems such as:
set cover and max coverage
metric Steiner tree and TSP
Steiner forest, Steiner network
Also a high-level overview of hardness of approximation.
The major techniques used for obtaining (guaranteed) approximation algorithms for NP-Complete problems in the past couple of decades (and prominent examples of their usage): LP-rounding, primal-dual, local ratio, etc., etc.
Assessment & Work
Several bi-weekly problem sets and a course project. The project can take the form of either an expository paper, a nontrivial implementation project, or (ideally) performing original research on a problem, which may be done in pairs.
The primary textbook used will be The Design of Approximation Algorithms (Williamson & Shmoys). Approximation Algorithms (Vazirani) is also recommended.