DIKU Bits: Cutting Cotton Compactly – a Computational Conundrum

Speaker

Mikkel Abrahamsen, Associate Professor in the Algorithms and Complexity section at the Department of Computer Science, University of Copenhagen

Title

Cutting Cotton Compactly – a Computational Conundrum

Abstract

You have a large roll of fabric and regularly receive orders with shapes of pieces to be cut out for clothing. Each time you have to decide where to cut the piece without knowing the next orders. Can the pieces be placed so that we don't waste much fabric? In the lecture, we will see that the answer is no in the following sense: For an arbitrarily large constant C, there is no algorithm that uses at most C times as much of the roll as would be sufficient if you knew all the orders to begin with.