Course Details

This semester, 522 will examine new topics and will be taught in a graduate seminar-like format.  A natural question that comes up is: How to design heuristics with provable approximation guarantees (error bounds) for specific NP-hard combinatorial optimization problems one often encounters in practice?  To this end, following a review of fundamental results, the course will briefly review fast approximation schemes for large structured packing and covering LPs, and then proceed through the list of specific topics (see 2015 Class URL), starting from the simpler paradigms of greedy, local search, dynamic programming, along with appropriate rounding procedures, to the more elaborate LP-based strategies, semidefinite programming, primal-dual methods, followed by deterministic or randomized rounding schemes.   The insight one gains by studying these topics often points ways to design high quality algorithms for new problems and applications.

The course is intended for students in computer science and in other disciplines such as mathematics, statistics, operations research, engineering, and bioinformatics.