A 2-approximation for 2D bin packing

We study the two|-dimensional geometrical bin packing problem (2DBP): given a list of rectangles, provide a packing of all these into the smallest possible number of $1\times1$ bins without rotating the rectangles. We present a $2$|-approximate algorithm, which improves over the previous best known ratio of $3$, matches the best results for the rotational case and also matches the known lower bound of approximability. Our approach makes strong use of a recently-discovered PTAS for a related knapsack problem and a new algorithm that can pack instances into $\OPT+2$ bins for any constant $\OPT$.

Logo BII

BII

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.