The course will offer the following themes:
• Introduction
Computational complexity of decision and optimization problems
NP-complete and NP-hard problems
Heuristic algorithms, quality of suboptimal solutions, (non)existence of a guarantee of quality
• Approximate solving of NP-hard problems
Approximation algorithms
Quality of approximate solutions
The class APX
Gap technique
Approximation schemes
The classes PTAS and FPTAS
Limits of approximate solving
• The design of approximation algorithms
Greedy method
Focusing on subproblems
Iterative partitioning
Dynamic programming
• Randomized solving of NP-hard problems
Las Vegas and Monte Carlo algorithms
The classes RP, co-RP, ZPP, PP, BPP
• The design of randomized algorithm
Random sampling
Establishing abundance of witnesses
Random reordering
Hashing
Load balancing
