The module aims to introduce students to the area of approximation and randomised algorithms, which often provide a simple and viable alternative to standard algorithms.
Students will learn the mathematical foundations underpinning the design and analysis of such algorithms.
By the end of the module, students should:
- Understand and use suitable mathematical tools to design approximation algorithms and analyse their performance.
- Understand and use suitable mathematical tools to design randomised algorithms and analyse their performance.
- Learn how to design faster algorithms with weaker (but provable) performance guarantees for problems where the best known exact deterministic algorithms have large running times.
- - Linearity of expectation, moments and deviations, coupon collector's problem
- - Chernoff bounds and its applications
- - Balls into bins, hashing, Bloom filters
- - The probabilistic method, derandomization using conditional expectations
- - Markov chains and random walks
- - LP duality, relaxations, integrality gaps, dual fitting analysis of the greedy algorithm for set cover.
- -The primal dual method: Set cover, steiner forest
- - Deterministic rounding of LPs: Set cover, the generalized assignment problem
- - Randomized rounding of LPs: Set cover, facility location
- - Multiplicative weight update method: Approximately solving packing/covering LPs