In real-world applications, many important practical problems are NP-hard, therefore it is expedient to consider not only the optimal solutions of NP-hard optimization problems, but also the solutions which are “close” to them (near-optimal solutions). So, we can try to design an approximation algorithm that efficiently produces a near-optimal solution for the NP-hard problem. In many cases we can even design approximation algorithms in such a way that the quality of the output is guaranteed to be within a constant factor (or function of the size of the input) of an optimal solution. This course is devoted to approximation algorithms for the Discrete Optimization problems.
- Teacher: KRZYSZTOF Pastuszak
- Teacher: Paweł Żyliński
