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.

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