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

The Taub Faculty of Computer Science Events and Talks

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