COMP760: Approximation Algorithms


Mohit Singh
Office: Room 324, McConnell Building
Contact: mohit (at) cs (dot) mcgill (dot) ca

Lectures and Office Hours

Lecture: TR 8:35-9:55AM10:00 AM-11:30AM, McConnell 320.
Office Hours: Wed 2:30-4:00PM, McConnell 324.

Course description:

The area of approximation algorithms deals with finding provable guarantees on the performance of heuristic solutions to hard combinatorial optimization problems. The course will present a variety of techniques that have been developed in the area of approximation algorithms ranging from dynamic programming, greedy methods, mathematical programming, randomization and metric methods.


Other References


  1. Homeworks 60%
  2. Final Exam 40%

Policy Statements

  1. Right to submit in English or French written work that is to be graded.
    In accord with McGill University's Charter of Students' Rights, students in this course have the right to submit in English or in French any written work that is to be graded.
  2. Academic Integrity statement.
    McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see ) for more information).