CSCI 550: Approximation Algorithms (Fall 2021)

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.


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



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 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.



Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: By appointment

Special Note for Fall 2021. In lieu of holding regularly-scheduled office hours, you are welcome to contact the instructor at any time via email to book a virtual meeting. See the course outline for details.