AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We study an interesting geometric optimization problem called Rectangle Packing with Area Maximization (RPA). We are given a set of rectangles and a rectangular target area called bin. The goal is to find a feasible packing of a subset of the given rectangles into the bin, i.e. an orthogonal packing without rotation and overlap. The objective is to maximize the total area of rectangles packed. This problem is a generalization of the Subset Sum problem, which is one of the most fundamental and well-known problems in combinatorial optimization and has many practical applications, such as VLSI layout and the cutting problem.

RPA is strongly NP-hard even for squares, therefore there is no fully polynomial time approximation scheme (FPTAS) for this problem, unless P=NP. The previously best result is a (1/2-epsilon)-approximation by Jansen & Zhang for our problem. We present a polynomial time approximation scheme (PTAS) for this problem, i.e. a family of algorithms which compute for any accuracy epsilon>0 in polynomial time a solution with ratio (1-epsilon).

Rolf Harren

--email hidden

passcode not visible

logged in users only