Roll cutting in the curtain industry : extended abstract

A. Alfieri, S.L. Velde, van de, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2005 : 13th annual european symposium, Palma de Mallorca, Spain, October 3-6, 2005 : proceedings
EditorsG.S. Brodal, S. Leonardi
Place of PublicationBerlin
ISBN (Print)3-540-29118-0
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Roll cutting in the curtain industry : extended abstract'. Together they form a unique fingerprint.

Cite this