Campus Event Calendar
Event Entry
What and Who
Cutting Christmas Cookies
Rolf Harren
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 9 April 2008
14:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Two-dimensional packing problems occur in everyday situations--at least once a year while cutting christmas cookies from the dough. As stars and trees are presumably difficult to handle, we restrict the shapes of the cookies to rectangles. In addition we disallow rotations by degrees different from 90°.
Consider the problem of cutting rectangular cookies from trays with dough, where the goal is to minimize the number of trays used. We present an algorithm for this problem with an absolute worst-case ratio of 2, which is optimal unless P = NP.
This is joint work with Rob van Stee.
Contact
Rolf Harren
--email hidden
passcode not visible
logged in users only
Uwe Brahm, 04/07/2008 14:54
Rolf Harren, 04/06/2008 18:40
Rolf Harren, 04/06/2008 18:39 -- Created document.
Rolf Harren, 04/06/2008 18:40
Rolf Harren, 04/06/2008 18:39 -- Created document.