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.

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

News

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, colouring Williamson & Shmoys, 2.1–2.4, 2.7
4 Rounding Data and Dynamic Programming: Knapsack, scheduling Williamson & Shmoys, 3.1–3.3
5 Deterministic Rounding: Scheduling, bin packing Williamson & Shmoys, 4.1–4.2, 4.6
6 Random Sampling and Randomized Rounding: MAX-SAT, MAX-CUT Williamson & Shmoys, 5.1–5.6
7 Randomized Rounding of Semidefinite Programs Williamson & Shmoys, 6.1–6.3, 6.5
8 Primal-Dual Method Williamson & Shmoys, 7.1–7.5
9 Metrics Williamson & Shmoys, 8.1–8.4
Fall study break
10 Student presentations
11 Student presentations
12 Student presentations

Assignments

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.

Personnel

Instructor

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.