Theory Seminar: Packing Small Vectors

Friday, January 15, 2016 - 2:00pm
CS 4310

Speaker Name: 

Ilan Cohen

Speaker Institution: 

Tel Aviv University

Cookies: 

Yes

Cookies Location: 

CS 4310

Description: 

Online d-dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, Memory, etc.). However, no online d-dimensional vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently small vectors, an O(log d)-competitive algorithm was known. We improve this to a constant competitive ratio, arbitrarily close to e \approx 2.718, given that vectors are sufficiently small.

We give improved results for the two dimensional case. For arbitrarily small vectors, the First Fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of First Fit variants, and for optimized parameters get a competitive ratio 1.48 for sufficiently small vectors.

We improve upon the 1.48 competitive ratio -- not via a First Fit variant -- and give a competitive ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors among arbitrarily many bins.

Joint work with: Yossi Azar, Amos Fiat, Alan Roytman