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
Jan 18 No classes (conference traveling)
Jan 19 No classes (conference traveling)
3 Jan 25 Duality
make-up class during tutorial
[GM] Ch. 4
4 Jan 26 SDP duality [GM] Ch. 4
Feb 1 Chinese New Year Holiday
Feb 2 Chinese 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
8 Feb 16 Cheeger–Alon–Milman inequality
9 Feb 22 Spectral embedding
10 Feb 23
11 Mar 1
12 Mar 2
13 Mar 8
14 Mar 9
15 Mar 15
16 Mar 16
17 Mar 22
18 Mar 23
19 Mar 29
20 Mar 30
21 Apr 5
22 Apr 6
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.

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.