๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An approximation scheme for strip packing of rectangles with bounded dimensions

โœ Scribed by W.Fernandez de La Vega; V. Zissimopoulos

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
597 KB
Volume
82
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

It is shown that for any positive E the strip-packing problem, i.e. the problem of packing a given list of rectangles into a strip of width 1 and minimum height. can be solled within I c 2: times the optimal height, in linear time, if the heights and widths of these rectangles are all bounded below by an absolute constant 2 >O.

๐Ÿ“œ SIMILAR VOLUMES

An approximation scheme for scheduling i
An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension
โœ Y. Kopidakis; V. Zissimopoulos ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 518 KB

We study the problem of scheduling independent jobs in a hypercube where jobs are executed in subcubes of various dimensions. The problem being NP-complete, several approximation algorithms based on list scheduling have been proposed, having approximation ratio of order of 2. In this paper, a linear