A 17/10-approximation algorithm for κ-bounded space on-line variable-sized bin packing

摘要

A version of the κ-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 for κ≥3.