דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Multiplicative Approximation Algorithms for Generalized Covering and Packing Problems
event speaker icon
יונתן וגנר, הרצאה סמינריונית למגיסטר
event date icon
יום רביעי, 9.7.2014, 13:00
event location icon
טאוב 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.
[בחזרה לאינדקס האירועים]