Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0675.68041
Chrobak, Marek; Ślusarek, Maciej
On some packing problem related to dynamic storage allocation. (English)
[J] RAIRO, Inf. Théor. Appl. 22, No.4, 487-499 (1988). ISSN 0988-3754

For a given list V of rectangles of height 1 in the Euclidean plane, these rectangles have to be packed by an algorithm A on-line (i.e. in order as they appear in the list) and nonintersecting. A(V) is defined to be the number of addresses used by A on data V. Let OPT(V) be the minimal number of addresses for packing V, for packing algorithms A. In the offline case the optimal solution can be trivially found in polynomial time. \par It is shown that there exists no algorithm A such that for some $\alpha,\beta >0$, $A(V)\le (3-\alpha)OPT(V)+\beta$, for any V. For the first-fit algorithm FF it is proved that there exist no $\alpha,\beta >0$ such that $FF(V)<(4-\alpha)OPT(V)+\beta$, for any V. The relations of these results to the dynamic storage allocation problem are considered.
[R.Klette]

MSC 2000:: *68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity

Keywords: dynamic storage allocation; rectangle packing; approximation algorithm

Cited in: Zbl 0755.68112

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]