Abstract:

We present and discuss the problem of placing a sequence of
disjoint  rectangles on a larger rectangle. In the formal definition 
of the problem, the inputs are the integral dimensions $L,H$ of (the
larger) rectangle $R$, and a sequence of natural numbers,
$J=j_1, j_2, ..., j_i$. The output is a sequence of rectangles,
$r_1, r_2,..., r_i$ placed in a disjoint fashion on $R$, such that
the area of  $r_k$ is smaller than or equal to $j_k$, $k=1, ..., i$.
Our goal is to place a maximal length prefix of $J$. In this talk, we 
briefly motivate the problem, then we show that the problem is hard. 
The main part of the talk is devoted to an approximation algorithm 
whose output satisfies: The area covered by all placed rectangles 
divided by the area covered by all rectangles in an optimal placement 
lies within a factor of $1- log(H)/H - 3/\sqrt{L} - \beta$. This
approximation ratio is achieved under the assumption that for each
$j_k$ it holds that $|j_k|<\beta S$, where $S=LH$.

This is a joint work with Dror Rawitz and Oran Sharon.