The maximum resource bin packing problem

摘要: Usually, for bin packing problems, we try to minimize the number of bins used or in case dual problem, maximize total size accepted items. This paper presents results opposite where would like We consider off-line and on-line variants problems. For variant, require that there be an ordering bins, so no item a later fits earlier bin. find approximation ratios two natural algorithms, First-Fit-Increasing First-Fit-Decreasing maximum resource variant classical packing. For define packing. For packing, algorithm is competitive. competitive ratio various algorithms. We study general versions problems as well parameterized upper bound $\frac{1}{k}$ on sizes, some integer k.