Contents may differ from the current or most recent offering of the course.
Course Description
Approximation algorithms are efficient algorithms that are guaranteed to compute solutions such that the value of the solution is provably close to the optimum. This course provides an introduction at the graduate level to the area of approximation algorithms, highlighting key algorithm design techniques for approximation algorithms and the complementary study of hardness of approximation for hard optimization problems.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 12:15pm–1:05pm; Wednesday, 11:15am–12:05pm; Thursday, 1:15pm–2:05pm
All lectures are held online.
Special Note for Fall 2021. We will not be scheduling synchronous lectures three times a week. See the course outline for details.
Textbook
D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms. Cambridge University Press, 2011.
The textbook is available for sale at the campus bookstore. A free electronic copy of a pre-publication edition of the textbook is available online. Course notes will also be provided for each lecture.
Marking Scheme
- Two assignments (20% each, total 40%)
- Student presentation (total 30%): a lesson plan (10%) and the presentation itself (20%)
- Report on the presentation (20%)
- Participation (total 10%)
News
- Nov. 1: Lecture notes for the ninth week have been posted.
- Oct. 25: Lecture notes for the eighth week have been posted.
- Oct. 18: Lecture notes for the seventh week have been posted. The second assignment has also been posted.
- Oct. 12: Lecture notes for the sixth week have been posted.
- Oct. 4: Lecture notes for the fifth week have been posted. Information about the student presentation/report assessments has also been posted.
- Sep. 27: Lecture notes for the fourth week have been posted.
- Sep. 20: Lecture notes for the third week have been posted.
- Sep. 13: Lecture notes for the second week have been posted. The first assignment has also been posted.
- Sep. 7: Lecture notes for the first week have been posted.
- Sep. 1: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Notes | Readings |
| 1 | Introduction: Set cover | Williamson & Shmoys, 1.1–1.6 |
| 2 | Computational Complexity | Williamson & Shmoys, App. B |
| 3 | Greedy Algorithms and Local Search: Scheduling, k-center, TSP, colouring | Williamson & Shmoys, 2.1–2.4, 2.7 |
| 4 | Rounding Data and Dynamic Programming: Knapsack, scheduling, bin packing | Williamson & Shmoys, 3.1–3.3 |
| 5 | Deterministic Rounding: Scheduling, simplex/ellipsoid methods | Williamson & Shmoys, 4.1–4.3 |
| 6 | Randomized Rounding of Linear Programs: MAX-SAT | Williamson & Shmoys, 5.1–5.4 |
| 7 | Randomized Rounding of Semidefinite Programs: MAX-CUT | Williamson & Shmoys, 5.1, 6.1–6.2 |
| 8 | Primal-Dual Method: Hitting set, feedback vertex set, shortest path | Williamson & Shmoys, 7.1–7.3 |
| 9 | Metrics: Multiway cuts, multicuts | Williamson & Shmoys, 8.1–8.3 |
| – | Fall study break | – |
| 10 | Student presentations | – |
| 11 | Student presentations | – |
| 12 | Student presentations | – |
Assignments
- Assignment 1, due Oct. 7
- Assignment 2, due Nov. 4
- Student Presentation, due date varies
- Report, due Dec. 6
Assignments are due by the due date indicated on the course Moodle page. Late assignments will be accepted up to 24 hours following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
The presentation and report must be submitted on the due date. Late submissions will not be accepted.
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: By appointment
Special Note for Fall 2021. In lieu of holding regularly-scheduled student hours, you are welcome to contact the instructor at any time via email to book a virtual meeting. See the course outline for details.