CMPUT 675 - Approximation Algorithms

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

Syllabus

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

The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge University Press, 2011.

It is available at the bookstore.

Scribe Notes

Template: .tex and .pdf

Schedule
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

Assignments

Assignment 0: Optional - Solution
Assignment 1: Due Sep 24 - Solution
Assignment 2: Due Oct 8 - Solution
Assignment 3: Due Oct 29 - Solution
Assignment 4: Due Nov 14 - Solution
Assignment 5: Due Dec 5 - Solution

Announcements

Dec 8: The last of the scribe notes have been added, assignment 5 solutions are available, and I added some pointers to further reading on expander graphs to the Nov 26 lecture notes.

Dec 1: The first part of the Max-2Lin(3) hardness notes are available. Please study them to get familiar with the ideas before next lecture.

Nov 20: Assignment 3 and 4 solutions are available.

Nov 18: Assignment 5 (the last one) is available.

Nov 4: An error in the illustration of N_i in Figure 1 on Assignment 4 has been corrected.

Oct 29: Assignment 4 is available.

Oct 20: There was a discrepancy in assignment 3 on the weight of question 1. This has been corrected.

Oct 16: Assignment 2 solutions are available now.

Oct 15: The project information is up. I will add more suggestions in the next few days.

Oct 15: A typo in question 1 part 3 of assignment 3 was fixed.

Oct 13: Assignment 3 is up. The background for the last question will be presented on either the 15th or 17th.

Sep 29: Assignment 1 solutions are available.

Sep 22: Assignment 2 is up. Good luck!

Sep 19: Solutions for assignment 0 are up. They are password protected, email me if you want the password.

Sep 17: Assignment 1, option 2 typo: "the odd degree nodes of D-{s,t}" should be "the odd degree nodes of V-{s,t}". The description is updated.

Sep 13: A brief description of Eulerian tours in directed graphs was added to Option 1 in Assignment 1.

Sep 13: The scribe template has been slightly updated to include an example of referencing a paper. Also, please let me know if you find any errors in the notes.

Sep 9: A scribe note schedule is up (link above). Sign up for a free slot by sending me an email (first come, first serve basis).

Sep 9: The syllabus was slightly updated again to indicate my office hours end at 3:00 pm on both days.

Sep 9: Assignment 1 is up. You get a couple of extra days to complete it since the necessary background will not be covered until tomorrow. Sorry it is slightly late, I had trouble uploading it from home last night.

Sep 8: I'm back from my trip. See you in class!

Sep 4: The lecture hours in the syllabus were incorrect. This is fixed.

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.

Iterative Methods in Combinatorial Optimization, Lap Chi Lau, R. Ravi, and Mohit Singh, Cambridge University Press, 2011.
Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009.
Approximation Algorithms, Vijay V. Vazirani, Springer-Verlag, Berlin, 2001.

Similar courses with nice scribe notes.

Approximation Algorithms and Approximability by Mohammad R. Salavatipour
Approximation Algorithms by Chandra Chekuri
Approximation Algorithms by Anupam Gupta and R. Ravi
Advanced Approximation Algorithms by Anupam Gupta and Ryan O'Donnell

Courses on related material with nice scribe notes.

Topics in Combinatorial Optimization by Chandra Chekuri
The PCP Theorem and Hardness of Approximation by Venkatesan Guruswami and Ryan O'Donnell
Linear and Semidefinite Programming by Anupam Gupta and Ryan O'Donnell