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.
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.
- Course Packet: Approximation Algorithms by David Williamson and David Shmoys. (Available from bookstore for course COMP 760)
- Approximation Algorithms by Vijay V. Vazirani
- Course Notes from Anupam Gupta and R. Ravi.
- Homeworks 60%
- Final Exam 40%
- 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.
- 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 www.mcgill.ca/students/srr/honest/ ) for more information).