A near-optimal solution to a two-dimensional cutting stock problem

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

Abstract:

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.

About this document ...

A near-optimal solution to a two-dimensional cutting stock problem

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

Footnotes

...Kenyon

Part of this work was done while the author was supported by CNRS and working at: LIP, ENS-Lyon, CNRS URA 1398, 46, allée d'Italie, 69364 Lyon Cedex 07, France.