Approximation and randomized algorithms

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