Anomalous behavior in bin packing algorithms
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.
- Best fit bin packing with random order revisited
- Truthful mechanism design for bin packing with applications on cloud computing
- Best fit bin packing with random order revisited
- A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint
- Near-optimal algorithms for stochastic online bin packing
- Classification and evaluation of the algorithms for vector bin packing
This page was built for publication: Anomalous behavior in bin packing algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115351)
