Approximation Algorithms


A large number of scenarios arising in communication, transportation, e-commerce, logistics etc. can be modeled as combinatorial optimization problems. Since most of these problem are NP-hard, one needs to design heuristics which run fast and find sufficiently good solutions. The goal of this course is to introduce a systematic study of such heuristics, called approximation algorithms, and develop a mathematical tool kit to analyze their worst case performances. The lectures also cover some barriers to approximability of problems.

  1. Students can design and analyze approximation algorithms for NP-hard problems
  2. Students can apply various mathematical tools in order to analyze worst case performance of approximation algorithms
  3. Students can analyze and prove the limitations to approximability of problems

Course Offering