Date 
Topic 
Reference 
Scribe 
Notes 
Sep 3,5 
Intro, Vertex Cover, Steiner Tree 
WS  Chapter 1.1 
Mohammad Salavatipour 
Lectured by Mohammad Salavatipour 
Sep 8 
Steiner Tree, Traveling Salesman Problem, .tex 
WS  Exercise 2.5, Chapter 2.4 
Zac Friggstad 

Sep 10 
Traveling Salesman Problem, .tex 
WS  Chapter 2.4 
Antonio Carlos Salzvedel Furtado Junior 

Sep 12 
kCentre and Set Cover, .tex 
WS  Chapters 2.2, 1.6 
Leah Hackman 

Sep 15 
Set Cover and Knapsack, .tex 
WS  Chapters 1.6, 3.1 
Bradley Hauer 

Sep 17 
Minimizing Makespan on Identical Parallel Machines, .tex 
WS  Chapter 3.2 
Chris Martin 

Sep 19 
Bin Packing Asymptotic PTAS, .tex 
WS  Chapter 3.3 
Yifeng Zhang 

Sep 22 
Linear Programming Introduction, .tex, figure 

Zac Friggstad 
See also LRS  Chapter 2.1. 
Sep 24 
Knapsack and MAX SAT, .tex 
WS  Chapter 5.3 
Nikos FasarakisHilliard 

Sep 26 
MAX SAT and Random Variables, .tex 
WS  Chapters 5.4, 5.5 
Antonio Carlos Salzvedel Furtado Junior 

Sep 29 
Chernoff Bounds and Minimizing Congestion, .tex 
WS  Chapters 5.10, 5.11 
Bradley Hauer 

Oct 1 
Separation Oracles and Multicut (Part 1), .tex 
WS  Chapter 8.3 
Chris Martin 

Oct 3 
Multicut (Part 2), .tex 
WS  Chapter 8.3 
Leah Hackman 

Oct 6,8 
LP Duality and Facility Location, .tex 
WS  Chapter 4.5 
Zac Friggstad 
See also V  Chapter 12 
Oct 10 
Multicut in Trees, .tex 
V  Chapter 18 
Nikos FasarakisHilliard 

Oct 15 
Steiner Forest, .tex 
WS  Chapter 7.4 
Yifeng Zhang 

Oct 17 
Steiner Forest and kMedian, .tex 
V  Chapters 7.4, 9.2 
Nikos FasarakisHilliard 

Oct 20 
kMedian, .tex 
WS  Chapter 9.2 
Zac Friggstad 

Oct 22 
Semidefinite Programming and Max Cut, .tex 
WS  Chapter 6.1, 6.2 
Zac Friggstad 

Oct 24 
NearlyTight Max Cut SDP Gap and Max 2SAT, .tex 
V  Example 26.12, Ch. 26.5 
Chris Martin 

Oct 27 
Colouring 3Colourable Graphs, .tex 
WS  Chapter 6.5 
Bradley Hauer 

Oct 29 
Tree Metrics  Part I, .tex 
WS  Chapter 8.5 
Leah Hackman 

Oct 31 
Tree Metrics  Part II, .tex 
WS  Chapter 8.5 
Yifeng Zhang 

Nov 3,5 
Group Steiner Tree, .tex 
GKR Paper 
Zac Friggstad 
We used simplifications from Rothvoss' Paper 
Nov 7,12 
kMST and PrizeCollecting Steiner Tree, .tex 
CRW Paper 
Zac Friggstad 
Also Exercise 14.1 and 14.2 in WS 
Nov 14 
Scheduling on Unrelated Machines, .tex 
LRS  Section 3.2 
Antonio Carlos Salzvedel Furtado Junior 
A different proof is Section 11.1 of WS 
Nov 17,19 
Bounded Degree Spanning Trees, .tex 
LRS  Section 4.4 
Zac Friggstad 
Also Section 11.2 in WS 
Nov 21,24 
Introduction to Hardness, .tex 
V  Sections 29.1 to 29.3 
Zac Friggstad 
Also Chapter 16 of WS 
Nov 26 
Maximum Independent Set Hardness, .tex 
V  Section 26.9 
Zac Friggstad 

Nov 28 
Set Cover Hardness, .tex 
WS  Sections 16.4 
Zac Friggstad 
Also Section 29.7 of V 
Dec 1,3 
HÃ¥stad's Max2Lin(3) Hardness, .tex 
AB  Section 26.9 
Zac Friggstad 
