Modern Approximation Algorithm

CSC

80070

Modern Approximation Algorithm

In the 1970s it was discovered that in addition to decision problems like SAT and Partition, many important discrete optimization problems are usually NP-Complete, and so are those unlikely to admit polynomial-time optimal algorithms. In such problems--e.g., traveling salesman, vertex cover, independent set, etc.--there is a large set of possible solutions and we search for a solution of minimum cost (or of maximum value).Since then, the theory of approximation algorithms has been developed. An approximation algorithm typically guarantees that, given any possible problem instance, the solution found will be within some constant (multiplicative) factor c of the optimal. It may be surprising that in the case of many optimization problems, it is possible to prove that our solutions will be close to optimal solution, even though we don't (and can't) know what optimal solution is. A set of fundamental techniques has emerged for designing and analyzing the performance of such approximation algorithms. In this course we will study these techniques and some of the most significant instances of their application. The core Algorithm course and certain level of mathematical maturity are prerequisites for this course.

Offer as needed

Graduate School Graduate

Yes