- Title
- Performance estimations of first fit algorithm for online bin packing with variable bin sizes and LIB constraints
- Creator
- Manyem, Prabhu; Lin, J. Y.; Sheu, Ruey-Lin
- Date
- 2005
- Type
- Text; Conference paper
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/53538
- Identifier
- vital:1463
- Abstract
- We consider the NP Hard problem of online Bin Packing while requiring that larger (or longer) items be placed below smaller (or shorter) items --- we call such a version the {LIB} version of problems. Bin sizes can be uniform or variable. We provide analytical upper bounds as well as experimental results on the asymptotic approximation ratio for the first fit algorithm.
- Publisher
- Ballarat, Victoria : University of Ballarat
- Relation
- Paper presented at the Sixteenth Australasian Workshop on Combinatorial Algorithms, Ballarat, Victoria : 18th - 21st September, 2005
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- Online approximation algorithm; Asymptotic worst case ratio; Bin packing problem; Longest item; Uniform sized bins; Variable sized bins
- Full Text
- Reviewed
- Hits: 815
- Visitors: 848
- Downloads: 73
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Published version | 5 MB | Adobe Acrobat PDF | View Details Download |