Check back soon for more information on the computer science seminar series. Unless otherwise noted, the seminars now meet on Mondays at 3pm in Stanley Thomas 302. If you would like to receive notices about upcoming seminars, you can subscribe to the announcement listserv.
Helmut Alt Freie Universität Berlin
Abstract: We consider the problem of placing geometric objects in two dimensions so that they occupy an area as small as possible. "Packing" means that the objects may overlap, "stacking" that they may not. Packing has important applications, e.g., in the clothing and steel industries. Reasonably efficient algorithms can be found if the number of objects to be placed is constant. If not, even the most simple variants of the problem are NP-hard, so it is important to find efficient approximation algorithms. In the talk, we will give an introduction into the problem, present its numerous variants, demonstrate its computational complexity, and present some approximation algorithms.
School of Science and Engineering, 201 Lindy Boggs Center, New Orleans, LA 70118 504-865-5764 firstname.lastname@example.org