The Taub Faculty of Computer Science Events and Talks

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.