CSCI5160 Approximation Algorithms — Spring 2018
Siu On CHAN Office hours Tuesday 2:304:30pm SHB 911
Teaching assistant
 Xiaojin ZHANG xjzhang@cse
News
 Apr 15: Project report will be due May 11 at 23:59. Please submit your report electronically to siuon@cse.
 Apr 4: Homework 2 is now posted.
 Feb 28: Homework 1 is now updated.
 Feb 22: Homework 1 is now updated.
 Feb 22: Homework 1 is now posted.
Information
 Lectures
 Mon 4:305:15pm (LSK 212) Thu 10:3012: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:
 Semidefinite programs
 SDP duality
 Multiplicative weight update
 Graph spectrum
 Cheeger–Alon–Milman inequality
 Random walks
 Local graph partitioning
 Expanders
 Laplacian solver
 Smallset expansion
 Effective resistance
 Sparsification
 Determinantal measures
 strong Rayleigh measures
 Random spanning trees
 Negative dependence
 Integrality gaps
 Hardness of approximation
 Matrix scaling
Lectures
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 makeup class (Wed 11:3012:15 LSK 304) 

16  Mar 8  Smallset 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 makeup class (Wed 11:3012: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 makeup class (Wed 11:3012: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 
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  Smallset 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 SinHang Engineering Building.
Project
The course project involves writing a short report (510 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 followup 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?
Paper suggestions:
 Fast Laplacian solver / maxflow
 AlmostLinearTime Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs, Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, Adrian Vladu
 The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach, Joel A. Tropp
 Approximate Undirected Maximum Flows in O(m polylog(n)) Time, Richard Peng
 Sparsification / expanders
 Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes, Adam W. Marcus, Nikhil Srivastava, Daniel A. Spielman
 Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates, Zeyuan AllenZhu, Zhenyu Liao, Lorenzo Orecchia
 A Matrix Expander Chernoff Bound, Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava
 Graph partitioning
 Local Flow Partitioning for Faster Edge Connectivity, Monika Henzinger, Satish Rao, Di Wang
 Graph Clustering using Effective Resistance, Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan
 Machine learning / sparse approximation
 Lowrank Optimization with Convex Constraints, Christian Grussler, Anders Rantzer, Pontus Giselsson
 Matrix Completion and Related Problems via Strong Duality, MariaFlorina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang
 Online algorithms
 A PrimalDual Randomized Algorithm for Weighted Paging, Nikhil Bansal, Niv Buchbinder , Joseph (Seffi) Naor
 Online Algorithms for Covering and Packing Problems with Convex Objectives, Yossi Azar, Niv Buchbinder, TH. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph (Seffi) Naor, Debmalya Panigrahi
 Tight Bounds for Approximate Carathéodory and Beyond, Vahab Mirrokni, Renato Paes Leme, Adrian Vladu, Sam ChiuWai Wong
 Hardness of approximation
 From GapETH to FPTInapproximability: Clique, Dominating Set, and More, Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
 Matrix scaling / operator scaling
 The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis, Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Akshay Ramachandran