CSCI5160 Approximation Algorithms — Spring 2020

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

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

Teaching assistant

News

Information

Lectures
Mon 2:30-4:15pm (ERB 405) Tue 3:30-4:15pm (LSB C5)
Prerequisites
Linear algebra, Probability, Discrete Math, algorithm design and analysis
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

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 6 Semidefinite programs and positive semidefinite matrices [GM] Ch. 2 Notes 01
2 Jan 7 SDP vs LP and Goemans–Williamson [GM] Ch. 1 Notes 02
3 Jan 13 Separation theorem, Polar set [BV] §2.5.1 Notes 03
4 Jan 14 Conjugate function [BV] §3.3 Notes 04
5 Jan 20 Dual program [BV] §4.1.1,§4.2,§5.1 Notes 05
6 Jan 21 Strong duality [BV] §5.1, §5.2, §5.3 Notes 06
Jan 27 Lunar New Year Holiday
Jan 28 Lunar New Year Holiday
Feb 3 Quarantine week
Feb 4 Quarantine week
Feb 10 Quarantine week
Feb 11 Quarantine week
7 Feb 17 Complementary slackness; KKT conditions [BV] §5.4, §5.5 Notes 07
8 Feb 18 Multiplicative Weight Update [AHK] §2, §3.3, §3.4 Notes 08
9 Feb 24 Graph spectrum and Laplacian Notes 09
10 Feb 25 Conductance, expansion, normalized Laplacian Lau’s lecture Notes 10
11 Mar 2 Cheeger–Alon–Milman inequality Lau’s or Spielman’s Notes 11
12 Mar 3 Random walk Lau’s lecture Notes 12
13 Mar 9 Local graph partitioning Lau’s lecture Notes 13
14 Mar 10 Local graph partitioning (continued) Lau’s lecture Notes 13
15 Mar 16 Expander Spielman’s or Lau’s Notes 15
16 Mar 17 Electrical flow and Laplace equation Spielman’s lecture Notes 16
17 Mar 23 Effective resistance
 Spielman’s or Lau’s Notes 17
18 Mar 24 Effective resistance (continued) Spielman’s or Lau’s Notes 17
19 Mar 30 Graph sparsification Lau’s or Spielman’s Notes 19
20 Mar 31 Sampling spanning trees by random walk Lau’s lecture Notes 20
21 Apr 6 Sampling spanning trees by random walk (continued) Lau’s lecture Notes 20
22 Apr 7 High dimensional expander Lau’s lecture Notes 22
Apr 13 Easter Monday
23 Apr 14 High dimensional expander (continued) Lau’s lecture Notes 22
24 Apr 20 High dimensional expander (continued) Lau’s lecture Notes 22
25 Apr 21 Largest simplex Nikolov Notes 25
26 Apr 27 Largest simplex (continued) Nikolov Notes 25
27 Apr 28 John ellipsoid Lau’s lecture Notes 27
Tentative schedule
Date Topic Readings Notes
1 Jan 6 Positive semidefinite matrices [GM] Ch. 2
2 Jan 7 Semidefinite programs and Goemans–Williamson [GM] Ch. 1
3 Jan 13 Duality [GM] Ch. 4
4 Jan 14 Duality
5 Jan 20 Duality
6 Jan 21 Multiplicative weights and minimizing regrets Arora–Hazan–Kale
Jan 27 Lunar New Year Holiday
Jan 28 Lunar New Year Holiday
7 Feb 3 Graph spectrum and Laplacian Lau’s lecture
8 Feb 4 Cheeger–Alon–Milman inequality Lau’s lecture
9 Feb 10 Spectral embedding Spielman’s lecture
10 Feb 11 Random walks Lau’s lecture
11 Feb 17 Random walks
12 Feb 18 Expanders Lau’s lecture
13 Feb 24 Local graph partitioning Lau’s lecture
14 Feb 25 Effective resistance Spielman’s lectures 7 & 8
15 Mar 2 Laplacian solver Lau’s lecture
Spielman’s lecture
16 Mar 3 Laplacian solver Lau’s lecture
Spielman’s lecture
17 Mar 9 Random walk and abstract simplicial complexes
18 Mar 10 Random walk and abstract simplicial complexes
19 Mar 16 John ellipsoid Lau’s lecture
20 Mar 17 John ellipsoid
21 Mar 23 Largest simplex Nikolov
22 Mar 24 Matrix scaling
23 Mar 30 Matrix scaling
24 Mar 31 Discrepancy minimization
25 Apr 6 Discrepancy minimization
26 Apr 7 TBD
Apr 13 Easter Monday
27 Apr 14 TBD

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.

Please submit your homework online as a single PDF file at elearn.cuhk.edu.hk

Homework 1 due Sun Mar 15 23:59 (updated on Mar 9 to fix typos in Q3: 4/n is now corrected as n/4)

Homework 2 due Sun May 10 at 23:59.

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.

Please submit your project report online as a single PDF file at elearn.cuhk.edu.hk by May 20 23:59

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

Write your summary as if you are explaining the main result and its key ideas to other students in this class, or to any graduate student with a solid background in math.

Explain in your own words and in simple language as much as possible. The more you can do so, the better you understand the papers.

Paper suggestions: