Anomalous behavior in bin packing algorithms (Q1115351)

An anomalous behaviour in some approximation algorithms for solving the bin packing problem is considered. Assume that \(Y=\{y_ 1,y_ 2,...,y_ n\}\) and \(X=\{x_ 1,x_ 2,...,x_ m\}\) are lists of items and \(s(y_ i)\) and \(s(x_ i)\) are the sizes of \(y_ i\) and \(x_ i\), respectively. The list Y dominates the list X if \(n\geq m\) and \(s(y_ i)\geq s(x_ i)\), \(1\leq i\leq m\). ALG(X) is the number of bins used by the bin packing algorithm ALG to pack the set X. An algorithm ALG is called monotonic if from ``Y dominates X'' follows that ALG(X)\(\leq ALG(Y)\). The author investigates monotonicity of some algorithms by using a dynamic dominance mapping. He gives upper bounds on the nonmonotonicity of some particular algorithms. Finally asymptotically tight bounds are derived for some well-known heuristics.