Multiplicative Approximation Algorithms for Generalized Covering and Packing Problems

Jonathan Wagner, M.Sc. Thesis Seminar
Wednesday, 9.7.2014, 13:00
Taub 601
Prof. E. Hazan

We present a simple scheme for width-independent multiplicative approximation algorithms for generalized covering and packing problems. We then present our main contribution- a novel sampling and acceleration technique for this scheme, which enables near-linear time algorithms. Applications of this result include near-linear time and width-free multiplicative approximation algorithms for fractional packing and covering problems and for normalized covering semi-definite programming.

Back to the index of events