CSCI5160 Approximation Algorithms — Spring 2017

Siu On CHAN Office hours Tuesday 3-5pm SHB 911

Teaching assistant

News

Information

Lectures
Wed 10:30-11:15pm (LSB G34) Thu 10:30-12:15pm (MMW 705)
References
  • [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys (available online)
  • [BV] Convex Optimization, Stephen Boyd and Lieven Vandenberghe (available online)
  • [G] Foundations of Optimization, Osman Güler (accessible online at university library webpage)
  • [GM] Approximation Algorithms and Semidefinite Programming, Bernd Gärtner and Jiri Matousek (accessible online at university library webpage)
Forum
Please sign up on Piazza
Grading
50% homeworks, 50% project, 5% bonus scribe notes

Topics

This course will study the design and analysis approximation algorithms for various optimization problems. We will cover spectral algorithms, semidefinite programs, and related convex programs. Here are tentative topics:

Lectures

Tentative schedule
Date Topic Readings Notes
1 Jan 11 Semidefinite programs [GM] Ch. 2 Notes 1
2 Jan 12 Goemans–Williamson rounding for Max-Cut [GM] Ch. 1 Notes 1 & 2
Jan 18 No classes (conference traveling)
Jan 19 No classes (conference traveling)
3 Jan 25 Duality
make-up class during tutorial
[GM] Ch. 4 Notes 3
4 Jan 26 SDP duality [GM] Ch. 4
Feb 1 Lunar New Year Holiday
Feb 2 Lunar New Year Holiday
5 Feb 8 Multiplicative weights and minimizing regrets
make-up class during tutorial
Arora–Hazan–Kale
6 Feb 9 Matrix multiplicative weights Arora–Kale
7 Feb 15 Graph spectrum and Laplacian
make-up class during tutorial
Lau’s lecture
8 Feb 16 Cheeger–Alon–Milman inequality Lau’s lecture
9 Feb 22 Spectral embedding Spielman’s lecture
10 Feb 23 Random walks Lau’s lecture
11 Mar 1 Random walks
12 Mar 2 Expanders Lau’s lecture
13 Mar 8 Local graph partitioning Lau’s lecture
14 Mar 9 Local graph partitioning
15 Mar 15 Small-set expanders and hypercontraction O’Donnell §9.4 & Cor. 8
16 Mar 16 Effective resistance Spielman’s lectures 7 & 8
17 Mar 22 Effective resistance Lau’s lecture
18 Mar 23 Graph sparsification Spielman’s lecture
19 Mar 29 Laplacian solver Lau’s lecture
Spielman’s lecture
20 Mar 30 Random spanning trees Oveis Gharan’s lecture
21 Apr 5 Traveling salesperson Oveis Gharan’s lecture
22 Apr 6 Largest simplex Nikolov
23 Apr 12
24 Apr 13

Homeworks

There will be two to three homeworks.

Collaboration on homework and consulting references is encouraged, but you must write up your own solutions in your own words, and list your collaborators and your references on the solution sheet.

Homework 1 due Thu Mar 16 in class

Project

The course project involves writing a short report (5-10 pages) related to approximation algorithms in an area of your interest. The report may be your exposition of a paper from the list below (or any similar paper), or a summary of your new follow-up results. You are encouraged include in your report any illustrative, concrete examples that help you understand the papers you read.