Talks
Fall 2016

Online Vector Packing

Tuesday, September 20th, 2016 2:10 pm3:00 pm

Add to Calendar

Location: 

Calvin Lab Auditorium 

Online $d$-dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, Memory, etc.). In this problem vectors arrives online and the goal is to assign them to minimum number of bins such that the sum of all vectors in each bin is at most the all $1$'s vector. We survey recent results on online vector packing such as lower and upper bounds for general vectors, lower and upper bounds for restricted size vectors and close to $e \approx 2.718$ upper and lower bounds for small vectors. Based on joint work with I. Cohen, S. Kamara, B. Shepherd (STOC'13), I. Cohen, A. Fiat, A. Roytman (SODA'16) and I. Cohen, and A. Roytman (2016)