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.
Description
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) NPComplete, and so are unlikely to admit polynomialtime optimal algorithms. In such problemse.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.
Prerequisites
Algorithms, and mathematical maturity.
Course Topics
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

multiway cut

knapsack

bin packing

vertex cover

scheduling problems

Steiner forest, Steiner network

facility location

multicommodity flow

MAXSAT
Also a highlevel overview of hardness of approximation.
Learning Goals
The major techniques used for obtaining (guaranteed) approximation algorithms for NPComplete problems in the past couple of decades (and prominent examples of their usage): LProunding, primaldual, local ratio, etc., etc.
Assessment & Work
Several biweekly 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.
Textbook
The primary textbook used will be The Design of Approximation Algorithms (Williamson & Shmoys). Approximation Algorithms (Vazirani) is also recommended.