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.
Vorschau
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:
Jansen, K., Solis-Oba, R., 2010. A simple OPT + 1 algorithm for cutting stock under the modified integer round-up property assumption, Bericht des Instituts für Informatik. Selbstverlag des Instituts für Informatik, Kiel.
Zitierform konnte nicht geladen werden.