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.
Students can design and analyze approximation algorithms for NP-hard problems
Students can apply various mathematical tools in order to analyze worst case performance of approximation algorithms
Students can analyze and prove the limitations to approximability of problems