Network and Combinatorial Optimization Algorithms

Course Description

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. Prerequisites: Familiarity with discrete structures, probability theory and design and analysis of algorithms, e.g., as in 01:198:205, 01:198:206, 01:198:344 or 16:198:512 or 16:198:513; or an equivalent background, in which case, contact the Instructor for Special Permission to register. (Those with < B in 513: first obtain an SP number). Knowledge of LP duality is useful but not a prerequisite.

Code

16:198:522

Credits

3

Subject

Computer Science