Academics

  /  

Courses

  /  

Descriptions

COMP_SCI 437: Approximation Algorithms

VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

COMP_SCI 212 and COMP_SCI 336 (or similar courses) or CS MS or CS PhDs

Description

This course studies approximation algorithms – algorithms that are used for solving hard optimization problems. Such algorithms find approximate (slightly suboptimal) solutions to optimization problems in polynomial time. Unlike heuristics, approximation algorithms have provable performance guarantees: they have bounds on the running time and on the quality of the obtained solutions. In this course, we will introduce various algorithmic techniques used for solving optimization problems such as greedy algorithms, local search, dynamic programming, linear programming (LP), semidefinite programming (SDP), LP duality, randomized rounding, and primal-dual analysis.

The course assumes background in basic probability theory and discrete mathematics. Key mathematical concepts will be reviewed before they are used.

• Formerly Comp_Sci 396/496 - last offer was Winter 2023
• This course fulfills Technical Elective area.
  

RECOMMENDED TEXTS:

• Approximation Algorithms by Vijay Vazirani.
• The Design of Approximation Algorithms by David Williamson and David Shmoys. A copy of this book is available online (http://www.designofapproxalgs.com/book.pdf).

COURSE INSTRUCTOR: Prof. Konstantin Makarychev