Multiplicative-Weights/Packing-Covering Method for Approximating Linear and Semidefinite Programs

Course Home Page:
Offered This Year?  No
When Offered? Occasionally


We will study the method called, variously, multiplicative weights and packing-covering. We will in particular investigate the use of this method for finding approximately optimal solutions to linear programs and semidefinite programs.

Students must have taken a graduate course on algorithms before taking this course.