ISYE 8813/ CS7520: Approximation Algorithms

Instructor

Mohit Singh
Office: Room 410, Groseclose Building
Contact: mohit.singh (at) isye (dot) gatech (dot) edu

Teaching Assistant

Uthaipon (Tao) Tantipongpipat
Office: Room 428, ISyE Main Building
Contact: tao (at) gatech (dot) edu

Lectures and Office Hours

Lecture: TR 9:30-10:45AM Groseclose 402.
Office Hours for Mohit Singh: F 3:00-4:00PM, Groseclose 410.
Office Hours for Uthaipon (Tao) Tatipongpipat: F 2:00-3:00PM, ISyE Main 428.

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.

Textbook

  • Approximation Algorithms by David Williamson and David Shmoys. Online Version freely available.

Other References

Grading

  1. Scribe 20%
  2. Homeworks 60%
  3. Project and Presentation 20%