@inproceedings{2940e58879924c8cbb6259f5126c911a,
title = "Roll cutting in the curtain industry : extended abstract",
abstract = "We study the problem of cutting a number of pieces of the same length from n rolls of different lengths so that the remaining part of each utilized roll is either sufficiently short or sufficiently long. A piece is sufficiently short, if it is shorter than a pre-specified threshold value d min, so that it can be thrown away as it cannot be used again for cutting future orders. And a piece is sufficiently long, if it is longer than a pre-specified threshold value d max (with d max¿>¿d min), so that it can reasonably be expected to be usable for cutting future orders of almost any length. We show that this problem, faced by a curtaining wholesaler, is solvable in O(n log n) time by analyzing a non-trivial class of allocation problems.",
author = "A. Alfieri and {Velde, van de}, S.L. and G.J. Woeginger",
year = "2005",
doi = "10.1007/11561071_27",
language = "English",
isbn = "3-540-29118-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "283--292",
editor = "G.S. Brodal and S. Leonardi",
booktitle = "Algorithms - ESA 2005 : 13th annual european symposium, Palma de Mallorca, Spain, October 3-6, 2005 : proceedings",
address = "Germany",
}