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

Rights

Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.

Cite

Citation style:
Could not load citation form.