(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

New Approximability Results for 2-Dimensional Packing Problems

Klaus Jansen
Institut für Informatik
Universität zu Kiel, Kiel, Germany

Tuesday, September 25, 2007, at 15:15
IMADA's Seminar Room

ABSTRACT

The strip packing problem is to pack a set of rectangles into a strip of fixed width and minimum length. In this talk we present asymptotic polynomial time approximation schemes for this problem without and with 90o rotations. The additive constant in the approximation ratios of both algorithms is 1, improving on the additive term in the approximation ratios of the algorithm by Kenyon and Rémila (for the problem without rotations) and Jansen and van Stee (for the problem with rotations), both of which have a larger additive constant O(1/ε2), ε > 0.

The algorithms were derived from the study of the rectangle packing problem: Given a set R of rectangles with positive profits, the goal is to find and pack a maximum profit subset of R into a unit size square bin [0,1] × [0,1]. We present algorithms that for any value ε > 0 find a subset R' ⊆ R of rectangles of total profit at least (1-ε) OPT, where OPT is the profit of an optimum solution, and pack them (either without rotations or with 90o rotations) into the augmented bin [0,1] × [0,1+ε]. This is joint work with Roberto Solis-Oba (Univ. of Western Ontario).

Host: Jørgen Bang-Jensen


SDU HOME | IMADA HOME | Previous Page
Last modified: Tue Sep 11 08:38:17 CEST 2007
Joan Boyar (joan@imada.sdu.dk)

 


   Data protection at SDUDatabeskyttelse på SDU