May 8, Tuesday
12:00 – 14:00
On the Complexity of Sequential Rectangle Placement In WIMAX
Computer Science seminar
Lecturer : Prof. Amos Israeli
Affiliation : Netanya College, CS
Location : 202/37
Host : Dr. Michael Elkin
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 of (the larger) rectangle , and a sequence of natural numbers, . The output is a sequence of rectangles, placed in a disjoint fashion on such that the area of is smaller than or equal to . Our goal is to place a maximal length prefix of . 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 . The complexity of the algorithm is linear. This is a joint work with Dror Rawitz and Oran Sharon.