BIN PACKING USING SEMI-ORDINAL DATA

Authors
LIU WP SIDNEY JB
Citation
Wp. Liu et Jb. Sidney, BIN PACKING USING SEMI-ORDINAL DATA, Operations research letters, 19(3), 1996, pp. 101-104
Citations number
5
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
19
Issue
3
Year of publication
1996
Pages
101 - 104
Database
ISI
SICI code
0167-6377(1996)19:3<101:BPUSD>2.0.ZU;2-M
Abstract
Algorithms for the bin packing problem are examined, under the ''ordin al assumption'': initially the values of the weights are unknown, but the ordering of the weights is known. It is shown that a worst case pe rformance ratio of rho (rho > 1 is an integer) can be achieved if [ln [n(rho - 1) + 1]/ln rho] weights among the n weights can be observed e xactly, where these weights are specified by their ranks among the set of weights.