CMPUT 675 - Approximation Algorithms - Fall 2014

Instructor: Zachary Friggstad
Contact Information: Click Here
Lecture: MWF 1:00 - 1:50 pm, CSC B 41
Office Hours: 2:00 - 3:00 pm on Monday and Tuesday


Resources: There is no required textbook, but many lectures will cover topics from the following. It is available at the bookstore.

Scribe Notes

Template: .tex and .pdf

Eventually, each student should provide notes for 3 lectures. You can sign up for a lecture at any time, but if you want to reserve your place in advance then pick an empty slot and send me an email. I will enter your name on the schedule.

WS = the Williamson and Shmoys textbook
LRS = the Lau, Ravi, and Singh text mentioned below
V = the Vazirani text mentioned below
AB = the Arora and Barak text mentioned below

Please point out any typos in the notes.

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   k-Centre 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 Fasarakis-Hilliard 
 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 Fasarakis-Hilliard 
 Oct 15   Steiner Forest, .tex   WS - Chapter 7.4   Yifeng Zhang    
 Oct 17   Steiner Forest and k-Median, .tex   V - Chapters 7.4, 9.2   Nikos Fasarakis-Hilliard 
 Oct 20   k-Median, .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   Nearly-Tight Max Cut SDP Gap and Max 2SAT, .tex   V - Example 26.12, Ch. 26.5   Chris Martin    
 Oct 27   Colouring 3-Colourable 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   k-MST and Prize-Collecting 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 Max-2Lin(3) Hardness, .tex   AB - Section 26.9   Zac Friggstad    



Project Information

Can be found here. Feel free to ask me for more project suggestions.

Additional Resources

Some texts that are related to topics we will cover. They are useful for further study in this field. Similar courses with nice scribe notes. Courses on related material with nice scribe notes.