EUR > Economics & Management > ESE > View Article
http://hdl.handle.net/1765/11691

scopus: cited 12 times
web of science: cited 13 times

Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem


Article
volume 39, issue 3 pp 201-217.
This publication is part of collection
Related Files
asset icon
(Hybrid_next-fit_algorithm.pdf, 0.7MB)

We present a new approximation algorithm for the two-dimensional bin-packing problem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e. g. if we open an new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.



Keywords


Automatically Extracted Terms
  • algorithm
  • height
  • h n f
  • rectangle
  • piece
  • problem
  • block
  • next-fit algorithm
  • list l
  • bin-packing
  • next-fit
  • interval
  • weight
  • a-type bin
  • b 2-type bin
  • frenk
  • sequence
  • proof
  • performance ratio
  • johnson


Bookmark with: