Optimal on-line algorithms for variable-sized bin covering

G.J. Woeginger, G. Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    14 Citations (Scopus)

    Abstract

    We deal with the variable-sized bin covering problem: Given a list L of items in (0,1] and a finite collection of feasible bin sizes, the goal is to select a set of bins with sizes in and to cover them with the items in L such that the total size of the covered bins is maximized. In the on-line version of this problem, the items must be assigned to bins one by one without previewing future items. This note presents a complete solution to the on-line problem: For every collection of bin sizes, we give an on-line approximation algorithm with a worst-case ratio , and we prove that no on-line algorithm can perform better in the worst case. The value mainly depends on the largest gap between consecutive bin sizes.
    Original languageEnglish
    Pages (from-to)47-50
    Number of pages4
    JournalOperations Research Letters
    Volume25
    Issue number1
    DOIs
    Publication statusPublished - 1999

    Fingerprint Dive into the research topics of 'Optimal on-line algorithms for variable-sized bin covering'. Together they form a unique fingerprint.

    Cite this