Multiplicative-Weights/Packing-Covering Method for Approximating Linear and Semidefinite Programs
|Offered This Year?||No|
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.