CSCI5160 Approximation Algorithms — Spring 2018

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

Siu On CHAN Office hours Tuesday 2:30-4:30pm SHB 911

Teaching assistant

News

Information

Lectures
Mon 4:30-5:15pm (LSK 212) Thu 10:30-12:15pm (LSB LT3)
References
  • [BV] Convex Optimization, Stephen Boyd and Lieven Vandenberghe (available online)
  • [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys (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, up to 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

Schedule
Date Topic Readings Notes
1 Jan 8 Positive semidefinite matrices [GM] Ch. 2 Notes 1 (draft)
2 Jan 11 Semidefinite programs and Goemans–Williamson [GM] Ch. 1 Notes 1 (draft)
3 Jan 15 Ellipsoid method Boyd’s lecture Notes 2 (draft)
4 Jan 18 Separation theorems [BV] §2.5.1
5 Jan 22 Farkas’ lemma Niemeier’s lecture
6 Jan 25 Strong duality [BV] §5.1, §5.2, §5.3
7 Jan 29 Multiplicative weights and minimizing regrets [AHK] §2, §3.3, §3.4
8 Feb 1 Multiplicative weights
9 Feb 5 Matrix multiplicative weights [AK] §6 or [AHK] §5
10 Feb 8 Graph spectrum and Laplacian Lau’s lecture
11 Feb 12 Cheeger–Alon–Milman inequality Lau’s or Spielman’s
Feb 15 Lunar New Year Holiday
Feb 19 Lunar New Year Holiday
12 Feb 22 Spectral embedding Spielman’s lecture
13 Feb 26 Random walks Lau’s lecture
14 Mar 1 Expanders Lau’s lecture
15 Mar 5 Local graph partitioning Lau’s lecture
* Mar 7 Local graph partitioning
make-up class (Wed 11:30-12:15 LSK 304)
16 Mar 8 Small-set expanders and hypercontraction O’Donnell §9.4 & Cor. 8
[CKL] §3
17 Mar 12 Fourier analysis and linearity test van Melkebeek’s 3 & 4
* Mar 14 Fourier analysis and linearity test
make-up class (Wed 11:30-12:15 LSK 304)
18 Mar 15 Hardness of approximation and Unique Games van Melkebeek’s or
Lau’s lecture
19 Mar 19 Resistor networks Spielman’s lectures 7 & 8
* Mar 21 Effective resistance
make-up class (Wed 11:30-12:15 LSK 304)		 Lau’s lecture
20 Mar 22 Graph sparsification Spielman’s lecture
21 Mar 26 Matrix Chernoff bound Harvey’s lecture
22 Mar 29 John ellipsoid Lau’s lecture
Apr 2 Easter Holiday
Apr 5 Ching Ming Festival
23 Apr 9 Largest simplex Nikolov
24 Apr 12 Matrix scaling Linial et al
Apr 16 Class canceled — traveling
Apr 19 Class canceled — traveling
Tentative schedule
Date Topic Readings Notes
1 Jan 8 Positive semidefinite matrices [GM] Ch. 2
2 Jan 11 Semidefinite programs and Goemans–Williamson [GM] Ch. 1
3 Jan 15 Duality [GM] Ch. 4
4 Jan 18 SDP Duality
5 Jan 22 Multiplicative weights and minimizing regrets Arora–Hazan–Kale
6 Jan 25 Matrix multiplicative weights Arora–Kale
7 Jan 29 Graph spectrum and Laplacian Lau’s lecture
8 Feb 1 Cheeger–Alon–Milman inequality Lau’s lecture
9 Feb 5 Spectral embedding Spielman’s lecture
10 Feb 8 Random walks Lau’s lecture
11 Feb 12 Random walks
Feb 15 Lunar New Year Holiday
Feb 19 Lunar New Year Holiday
12 Feb 22 Expanders Lau’s lecture
13 Feb 26 Local graph partitioning Lau’s lecture
14 Mar 1 Small-set expanders and hypercontraction O’Donnell §9.4 & Cor. 8
15 Mar 5 Unique Games and hardness of approximation
16 Mar 8 Effective resistance Spielman’s lectures 7 & 8
17 Mar 12 Effective resistance Lau’s lecture
18 Mar 15 Graph sparsification Spielman’s lecture
19 Mar 19 Laplacian solver Lau’s lecture
Spielman’s lecture
20 Mar 22 John ellipsoid Lau’s lecture
21 Mar 26 John ellipsoid
22 Mar 29 Largest simplex Nikolov
Apr 2 Easter Holiday
Apr 5 Ching Ming Festival
23 Apr 9 Real stable polynomials
24 Apr 12 Real stable polynomials
25 Apr 16 Matrix scaling
26 Apr 19 Matrix scaling

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 Mon Mar 5 in class (updated on Feb 22 to fix a typo in Q1 and added a clarifying question in Q4; updated on Feb 28 to fix an error in Q5)

Homework 2 due Thu Apr 19 at 23:59. 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.

If your report is a summary of a paper you read, it should highlight the following:

Paper suggestions: