Fractal Beauty of Bin Packing; Software engineering rept

摘要

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) (sigma) (0, 1), are used is studied in detail. This investigation leads us to the discovery of several interesting fractal-like curves.