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

J.B.G. Frenk, G. Galambos

    Research output: Book/ReportReportAcademic

    337 Downloads (Pure)

    Abstract

    We present a new approximation algorithm for the two-dimensional bin-packing probIem. 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 a 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.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages14
    Publication statusPublished - 1986

    Publication series

    NameMemorandum COSOR
    Volume8619
    ISSN (Print)0926-4493

    Fingerprint Dive into the research topics of 'Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem'. Together they form a unique fingerprint.

    Cite this