CSCI5160 Approximation Algorithms — Spring 2017

This is the webpage for a previous offering of the course in 2017; latest offering available here

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 Random spanning trees
22 Apr 6 Determinantal measures and negative dependence Oveis Gharan’s lecture
23 Apr 12 Traveling salesperson Oveis Gharan’s lecture
24 Apr 13 John ellipsoid Lau’s lecture
25 Apr 21 John ellipsoid
26 Apr 22 Largest simplex Nikolov

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

Homework 2 due Sun Apr 23 at 23:59 (updated to fix typos and a mistake in Q5(b) on Apr 17). Please submit to 9th floor assignment box in Ho Sin-Hang Engineering Building.

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.