News
- Mar 8: Assignment 2 is now posted
- Feb 1: Assignment 1 is now posted
Information
- Online lectures
- Mon 2:30-4:15pm Tue 3:30-4:15pm
- Online tutorials
- Tue 4:30-5:15pm (Certain weeks only)
- Zoom
-
939 9035 1363 (for both lectures and tutorials)No passcode, but CUHK-authenticated Zoom accounts are required to join
- Instructor
- Siu On CHAN Office hours: Thu 4:30-6:30pm (Zoom 984 7747 9788)
- Teaching assistant
-
Qinghua DING
qhding@cse - Prerequisites
- Linear algebra, Probability, Discrete Math, Algorithm Design and Analysis
- References
- [BV] Convex Optimization, Stephen Boyd and Lieven Vandenberghe (available online)
- [GM] Approximation Algorithms and Semidefinite Programming, Bernd Gärtner and Jiri Matousek (accessible online at the university library webpage)
- [S] Spectral and Algebraic Graph Theory, Daniel A. Spielman (available online)
- Additional references
- [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 the university library webpage)
- Forum
- Please sign up on Piazza
- Grading
- 50% homework, 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:
- Semidefinite programs
- SDP duality
- Multiplicative weight update
- Graph spectrum
- Eigenvalue interlacing
- Cheeger–Alon–Milman inequality
- Random walks
- Local graph partitioning
- Expanders
- Laplacian solver
- Effective resistance
- Sparsification
- Matrix scaling
- Abstract simplicial complex
- Random spanning trees
Lectures
Lecture recordings will be posted on Piazza → Resources after classes
| Date | Topic | Readings | Notes | ||
|---|---|---|---|---|---|
| 1 | Jan 11 | Positive semidefinite matrices | [GM] Ch. 2 | ||
| 2 | Jan 12 | Semidefinite programs and Goemans–Williamson | [GM] Ch. 1 | ||
| 3 | Jan 18 | Separation theorems, Polar sets | [GM] Ch. 4 | ||
| 4 | Jan 19 | Conjugate function | [BV] §3.3 | ||
| 5 | Jan 25 | Dual program | [BV] §4.1.1,§4.2,§5.1 | ||
| 6 | Jan 26 | Strong duality | [BV] §5.1,§5.2,§5.3 | ||
| 7 | Feb 1 | Complementary slackness; KKT conditions | [BV] §5.4, §5.5 | ||
| 8 | Feb 2 | Multiplicative Weight Update | Arora–Hazan–Kale | ||
| 9 | Feb 8 | Graph spectrum and Laplacian | [S] Ch. 2.1, 3.1, 4.1-4.3 | ||
| 10 | Feb 9 | Conductance, expansion, normalized Laplacian | [S] Ch. 20 | ||
| Feb 15 | Lunar New Year Holiday | ||||
| Feb 16 | Lunar New Year Holiday | ||||
| 11 | Feb 22 | Cheeger–Alon–Milman inequality | [S] Ch. 21 | ||
| 12 | Feb 23 | Cheeger–Alon–Milman inequality | [S] Ch. 21 | ||
| 13 | Mar 1 | Random walk | [S] Ch. 10 | ||
| 14 | Mar 2 | Random walk | [S] Ch. 10 | ||
| 15 | Mar 8 | Local graph partitioning | [S] Ch. 22 | ||
| 16 | Mar 9 | Local graph partitioning | [S] Ch. 22 | ||
| 17 | Mar 15 | Expanders | [S] Ch. 27 | ||
| 18 | Mar 16 | Electrical flow and Laplace equation | [S] Ch. 11 | ||
| 19 | Mar 22 | Effective resistance | [S] Ch. 12 | ||
| 20 | Mar 23 | Effective resistance | [S] Ch. 12 |
| Date | Topic | Readings | Notes | |
|---|---|---|---|---|
| 1 | Jan 11 | Positive semidefinite matrices | [GM] Ch. 2 | |
| 2 | Jan 12 | Semidefinite programs and Goemans–Williamson | [GM] Ch. 1 | |
| 3 | Jan 18 | Separation theorems, Polar sets | [GM] Ch. 4 | |
| 4 | Jan 19 | Conjugate function | [BV] §3.3 | |
| 5 | Jan 25 | Dual program, Strong duality | [BV] §4.1.1,§4.2,§5.1,§5.2,§5.3 | |
| 6 | Jan 26 | Complementary slackness; KKT conditions | [BV] §5.4, §5.5 | |
| 7 | Feb 1 | Multiplicative Weight Update | Arora–Hazan–Kale | |
| 8 | Feb 2 | Multiplicative Weight Update | Arora–Hazan–Kale | |
| 9 | Feb 8 | Graph spectrum and Laplacian | Lau’s lecture | |
| 10 | Feb 9 | Conductance, expansion, normalized Laplacian | Lau’s lecture | |
| Feb 15 | Lunar New Year Holiday | |||
| Feb 16 | Lunar New Year Holiday | |||
| 11 | Feb 22 | Cheeger–Alon–Milman inequality | Lau’s lecture | |
| 12 | Feb 23 | Random walks | Lau’s lecture | |
| 13 | Mar 1 | Local graph partitioning | Lau’s lecture | |
| 14 | Mar 2 | Local graph partitioning | Lau’s lecture | |
| 15 | Mar 8 | Expanders | Lau’s lecture | |
| 16 | Mar 9 | Effective resistance | Spielman’s lectures 7 & 8 | |
| 17 | Mar 15 | Electrical flow and Laplace equation | Spielman’s lecture | |
| 18 | Mar 16 | Graph sparsification | Lau’s or Spielman’s | |
| 19 | Mar 22 | Sampling spanning trees | Lau’s lecture | |
| 20 | Mar 23 | Sampling spanning trees | ||
| 21 | Mar 29 | High dimensional expander | Lau’s lecture | |
| 22 | Mar 30 | High dimensional expander | ||
| Apr 5 | Day after Chung Ming Festival | |||
| Apr 6 | Day after Easter Monday | |||
| 23 | Apr 12 | Matrix scaling | ||
| 24 | Apr 13 | Matrix scaling | ||
| 25 | Apr 19 | TBD | ||
| 26 | Apr 20 | TBD |
Homework
There will be three homework assignments
Submit your answers as a single PDF file via Blackboard by 11:59pm
You are encouraged to either typeset your solution in LaTeX or Word, or scan or take photos of your handwritten solution (please bundle your scans/photos into a single PDF file)
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
- Assignment 1 due Wed Feb 17 23:59
- Assignment 2 due Sun Mar 21 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.
If your report is a summary of a paper you read, it should highlight the following:
- What is the main result? A typical paper contains one main result and several corollaries or extensions. Focus on the main result in your report, unless you find a particular extension interesting.
- If the main result is very general, can you illustrate it with interesting special cases?
- What are the key new ideas? Can you illustrate them with concrete examples? How did the authors come up with these ideas?
- What have you learned? How might the key ideas or new results be useful in your own research?
- Are key inequalities in the papers tight (perhaps up to constant factors)? If so, can you come up with tight examples? If not, what do you think are the correct bounds?
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: