Tight bounds for restricted grid scheduling
From MaRDI portal
Abstract: The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remaining which fits in it when the bin arrives. The goal is to minimize the total size of all the bins used. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved using jobs of size S and 2S-1. For these item sizes and maximum bin size 4S-3, we obtain asymptotically matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.
Recommendations
Cites work
- A lower bound for on-line bin packing
- A new variable-sized bin packing problem
- A new version of on-line variable-sized bin packing
- Competitive snoopy caching
- scientific article; zbMATH DE number 1232130 (Why is no real title available?)
- More on online bin packing with two item sizes
- On-line bin packing with two item sizes
- Online variable-sized bin packing with conflicts
- Scheduling jobs on grid processors
Cited in
(3)
This page was built for publication: Tight bounds for restricted grid scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384122)
