Jonathan Wagner, M.Sc. Thesis Seminar
Wednesday, 9.7.2014, 13:00
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.