Multiplicative Approximation Algorithms for Generalized Covering and Packing Problems

יונתן וגנר, הרצאה סמינריונית למגיסטר
יום רביעי, 9.7.2014, 13:00
טאוב 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.

בחזרה לאינדקס האירועים