COMP_SCI 396, 496: Advanced Topics in Approximation Algorithms

Quarter Offered

None : 10-1 F ; Makarychev


Undergraduate students need permission of instructor.


This course studies advanced topics in approximation algorithms. 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 discuss cutting edge research on approximation algorithms and related fields. Students will read and present papers from recent theoretical computer science conferences and present them in class. We will also explore open questions and promising research directions in theoretical computer science.

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


COURSE INSTRUCTOR: Prof. Konstantin Makarychev