CSCI 550: Approximation Algorithms (Fall 2022)

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 in Immaculata Hall, room 202.


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 Introduction (cont’d); 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 at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class 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: Monday, 9:15am–11:15am