link

March 23, Tuesday
12:00 – 14:00

Optimal Online Bounded Space Multidimensional Packing
Computer Science seminar
Lecturer : Dr. Lea Epstein
Lecturer homepage : http://www.tau.ac.il/~lea/
Affiliation : Interdisciplinary Center in Herzliya
Location : -101/58
Host : Dr. Eitan Bachmat
We introduce several on-line multidimensional bin packing models and discuss the unique properties of each one of them. Then we concentrate on the oriented bounded space model and describe the results in more detail. For this model we present an algorithm of tight asymptotic performance ratio both for the general case of hyperbox packing, and the more special case of hypercube packing. This ratio is exponential in the dimension for hyperboxes, but sub-linear for hypercubes.

Most results presented in this talk are based on a joint work with Rob van Stee.