Skip to main content Skip to navigation

CS356 Approximation and Randomised Algorithms

Academic Aims

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.

Learning Outcomes

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.

Content

  • - 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

15 CATS (7.5 ECTS)
Term 2

Organiser:
Sayan Bhattacharya

Syllabus

Online material