IBM Israel Research Seminars

We present and discuss the problem placing a sequence of disjoint rectangles on a larger rectangle. In the formal definition of the problem, the inputs are the integral dimensions L x H of (the larger) rectangle R, and a sequence of natural numbers, J = j₁, j₂, ..., j_i. The output is a sequence of rectangles, r₁, ..., r_j placed in a disjoint fashion on R such that the area of r_i is smaller than or equal to j_i. Our goal is to place a maximal length prefix of J. In this talk, we briefly motivate the problem, than we show 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:

This approximation ratio is achieved under the assumption that for each where S = L · H. The complexity of the algorithm is linear.

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

About the speaker
Short Bio Amos Israeli is the dean of the school for Computer Science and Mathematics in Netanya College. Amos joined Netanya College in 1997. Before that he was at the Technion and at intel. His interests are Algorithms, mainly distributed, and Software.