CS 369A: Advanced Approximation Algorithms

Instructor: Moses Charikar (Office hours: by appointment, Gates 462.)

Time/location: 1:30-3:20pm on Tuesdays in 380-380W .

Discussion: We will use Piazza for discussion and announcements. Sign up here:
piazza.com/stanford/winter2016/cs369a

Course description:
Optimization problems are ubiquitous, yet most are NP-hard to solve exactly. One popular approach to circumvent this intractability is to design approximation algorithms, i.e. efficient algorithms that produce solutions with value close to the optimum. This course will cover major advances in the field of approximation algorithms in the past decade or so.

Prerequisites:
Students will be expected to have a strong background in algorithms and probability. Familiarity with basic approximation algorithms (or permission of instructor).

Course requirements:
3-4 problems sets and possibly a paper presentation.

Tentative Syllabus
The course will introduce a number of techniques in the context of approximation algorithms for some central problems in the area. Here is a representative sample of techniques and problems we will discuss.

Techniques:

• Graph approximation by trees
• Multiplicative weight update
• Iterative rounding
• Spectral methods
• Algorithmic Lovasz local lemma
• Hierarchies of LP and SDP relaxations

Problems:

• Graph partitioning
• Network design
• Oblivious routing
• Steiner tree
• Unique games
• Densest subgraph
• Minimum discrepancy
• Scheduling

Reference:
We will refer to these texts, as well as recent papers

• "Approximation Algorithms" by Vijay Vazirani
  Electronic version available here .
• "The Design of Approximation Algorithms" By David P. Williamson and David B. Shmoys
  Electronic version available here .
• "Iterative Methods in Combinatorial Optimization" by Lap Chi Lau, R. Ravi, and Mohit Singh
  Electronic version available here

Lecture Schedule:

1. Jan 5
• Oblivious routing, capacity approximation of graphs via trees [WS 15.2]
• I mentioned pseudo-approximations for min bisection. [WS 8.4] describes these approaches, building on machinery described in [WS 8.3]
2. Jan 12
• O(log n) approximation for min bisection [WS 15.3]
• Probabilistic approximation of metrics by tree metrics [WS 8.5]
3. Jan 19
• Iterated rounding: min-cost degree bounded spanning tree [WS 11.2]
4. Jan 26
• Discrepancy (references on piazza)
5. Feb 2
• Grothendieck Inequality (references on piazza)
6. Feb 9
• Sparsest Cut: Arora Rao Vazirani [WS 15.4]
7. Feb 16
• Unique Games hardness for Max Cut (references on piazza)
8. Feb 23
• Unique Games continued (references on piazza)
9. Mar 1
• Lift-and-project hierarchies (references on piazza)
10. Mar 8
• Lower bounds on extended formulations (references on piazza)

Related courses:

• Approximation Algorithms by Amin Saberi.
• Linear and Semi-Definite Programming in Approximation Algorithms by Konstantin Makarychev and Mohit Singh.