Show The Graduate Center Menu
 
 

Modern Approximation Algorithms

Instructor: Assistant Professor Matthew Johnson

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) 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.
 

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:

  • greedy algorithms

  • local search

  • PTASs

  • LP rounding

  • randomized rounding

  • primal-dual

  • local ratio

  • factor-revealing LPs

  • SDP rounding

  • grid-shifting/treewidth PTASs
     

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

  • MAX-SAT
     

Also a high-level overview of hardness of approximation.
 

Learning Goals

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.
 

Textbook

The primary textbook used will be The Design of Approximation Algorithms (Williamson & Shmoys). Approximation Algorithms (Vazirani) is also recommended.