Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Structural Lemma in 2-Dimensional Packing, and its Implications on Approximability
Speaker:Lars Prädel
coming from:University of Kiel
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 27 November 2009
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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).

Contact
Name(s):Rolf Harren
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Rolf Harren, 11/12/2009 03:23 PM
  • Rolf Harren, 11/12/2009 03:22 PM -- Created document.