Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Multiplicative Approximation Algorithms for Generalized Covering and Packing Problems
event speaker icon
Jonathan Wagner, M.Sc. Thesis Seminar
event date icon
Wednesday, 9.7.2014, 13:00
event location icon
Taub 601
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]