Repacking helps in bounded space on-line bind-packing

G. Galambos, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    28 Citations (Scopus)

    Abstract

    We consider a version of the on-line bounded-space bin-packing problem where repacking the items within the active bins is allowed. For this problem, the 1.69103 lower bound of Lee and Lee [7] for the worst case ratios of bounded-space approximation algorithms still applies. We present a polynomial time approximation algorithm that reaches the best possible worst case ratio matching the Lee and Lee lower bound while using onlythree active bins. Wir behandeln eine Variante des On-Line Bound-Space Bin-Packings, in der das Umpacken der Gegenstände innerhalb der aktiven Bins erlaubt ist. Auch für diese Variante gilt die untere Schranke 1.69103, die Lee und Lee [7] für Worst Case Ratios von Bounded-Space Approximations-Algorithmen bewiesen haben. Wir konstruieren einen bestmöglichen polynomialen Approximations-Algorithmus, der die Schranke von Lee und Lee erreicht und dazu nurdrei aktive Bins verwendet.
    Original languageEnglish
    Pages (from-to)329-338
    Number of pages10
    JournalComputing
    Volume49
    Issue number4
    DOIs
    Publication statusPublished - 1993

    Fingerprint

    Dive into the research topics of 'Repacking helps in bounded space on-line bind-packing'. Together they form a unique fingerprint.

    Cite this