On-line bin packing : a restricted survey

G. Galambos, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    50 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    In the classical bin packing problem, one is asked to pack items of various sizes into the minimum number of equal-sized bins. In the on-line version of this problem, the packer is given the items one by one and must immediately and irrevocably assign every item to its bin, without knowing the future items. Beginning with the first results in the early 1970's, we survey - from the worst case point of view - the approximation results obtained for on-line bin packing, higher dimensional versions of the problem, lower bourds on worst case ratios and related results.
    Original languageEnglish
    Pages (from-to)25-45
    Number of pages21
    JournalMathematical Methods of Operations Research
    Volume42
    Issue number1
    Publication statusPublished - 1995

    Fingerprint

    Dive into the research topics of 'On-line bin packing : a restricted survey'. Together they form a unique fingerprint.

    Cite this