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

### 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%): participation in class (5%) and reviewing student presentations (5%)

## News

- Nov. 3: Lecture notes for the ninth week have been posted.
- Oct. 27: Lecture notes for the eighth week have been posted.
- Oct. 20: Lecture notes for the seventh week have been posted.
- Oct. 17: Assignment 2 has been posted. It is due by Nov. 3 at 1:15pm.
- Oct. 13: Lecture notes for the sixth week have been posted.
- Oct. 6: Lecture notes for the fifth week have been posted.
- Oct. 3: Information about the student presentation/report assessments has been posted.
- Sep. 29: Lecture notes for the fourth week have been posted.
- Sep. 26: Due to the inclement weather over the weekend, both office hours and the lecture today are cancelled.
- Sep. 22: Lecture notes for the third week have been posted.
- Sep. 19: Due to the delayed opening of the university today, office hours for this morning are cancelled.
- Sep. 15: Lecture notes for the second week have been posted. Assignment 1 has also been posted. It is due by Oct. 6 at 1:15pm.
- Sep. 8: Lecture notes for the first week have been posted.
- Sep. 1: Welcome to the course! The first lecture is on Sep. 7.

## Lectures

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

- Assignment 1, due Oct. 6
- Assignment 2, due Nov. 3
- Student Presentation, due date varies
- Report, due Dec. 5

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.

## Personnel

### Instructor

Taylor J. Smith

Email: tjsmith [at] stfx [dot] ca

Office: Annex, Room 9A

Office hours: Monday, 9:15am–11:15am