Bin packing using semi-ordinal data

Algorithms for the bin packing problem are examined, under the ‘ordinal assumption’: initially the values of the weights are unknown, but the ordering of the weights is known. It is shown that a worst case performance ratio of ρ (ρ > 1 is an integer) can be achieved if ⌊ln [n(ρ – 1) + 1]/ln ρ⌋ weights among the n weights can be observed exactly, where these weights are specified by their ranks among the set of weights.