On the fractal beauty of bin packing
In the variable-sized online bin packing problem, one has to assign items to bins one by one. The bins are drawn from some fixed set of sizes, and the goal is to minimize the sum of the sizes of the bins used. We present the first unbounded space algorithms for this problem. We also show the first lower bounds on the asymptotic performance ratio. The case where bins of two sizes, 1 and $alpha in (0,1)$, are used is studied in detail. This investigation leads us to the discovery of several interesting fractal-like curves.
|Nonnumerical Algorithms and Problems (acm F.2.2)|
|Analysis of algorithms and problem complexity (msc 68Q25), Approximation algorithms (msc 68W25), Analysis of algorithms (msc 68W40)|
|Software Engineering [SEN]|
Epstein, L, Seiden, S, & van Stee, R. (2001). On the fractal beauty of bin packing. Software Engineering [SEN]. CWI.