Claire Kenyon
LRI, Bât. 490, Université Paris XI
91405 ORSAY, France.
Email: kenyon@lri.lri.fr
-
Eric Rémila
Grima, IUT Roanne (Université J. Monnet)
20 avenue de Paris, 42334 Roanne, France.
or
LIP, ENS-Lyon, CNRS URA 1398,
46, allée d'Italie, 69364 Lyon Cedex 07, France.
Email: remila@univ-st-etienne.fr
We present an asymptotic fully polynomial approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP-hard cutting-stock problem. Given any e, The algorithm, based on a reduction to fractional bin-packing, finds a packing of n rectangles whose total height is within a factor of 1+e of optimal (up to an additive term), and has running time polynomial both in n and in 1/e.
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -dir /users/algo/kenyon/WWW/Publis/ -split 0 MOR-abstract.tex.
The translation was initiated by Claire Kenyon on 3/19/1998