- Title
- Online LIB problems : Heuristics for bin covering and lower bounds for bin packing
- Creator
- Finlay, L.; Manyem, Prabhu
- Date
- 2005
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/44653
- Identifier
- vital:285
- Identifier
-
https://doi.org/10.1051/ro:2006001
- Identifier
- ISSN:0399-0559
- Abstract
- We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items - we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered.; C1
- Publisher
- EDP Sciences
- Relation
- Rairo-Operations Research Vol. 39, no. 3 (Jul-Sep 2005), p. 163-183
- Rights
- Centre for Informatics and Applied Optimisation (CIAO)
- Rights
- Copyright EDP Sciences
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0102 Applied Mathematics; Online approximation algorithm; Asymptotic worst case ratio; Bin covering problem; Bin packing problem; Longest item; Uniform sized bins
- Full Text
- Reviewed
- Hits: 1036
- Visitors: 1469
- Downloads: 440
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | DS1 | Final Version | 251 KB | Adobe Acrobat PDF | View Details Download |