A simple OPT + 1 algorithm for cutting stock under the modified integer round-up property assumption

We present a simple algorithm for the cutting stock problem with a constant number d of object sizes that produces solutions of value at most OPT +1 in time d^{O(d)} log^7 n, where OPT is the value of an optimum solution. This algorithm works under the assumption that the modified integer round-up property of Scheithauer and Terno for the cutting stock problem holds.

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.