Max-Planck-Institut für Informatik
max planck institut
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:On approximating strip packing with a better ratio than 3/2
Speaker:Andreas Wiese
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 19 July 2016
Duration:30 Minutes
Building:E1 4
(joint work with Giorgi Nadiradze)

In the strip packing problem we are given a set of rectangular items that we want to place in a strip of given width such that we minimize the height of the obtained packing. It is a very classical two-dimensional packing problem that has received a lot of attention and it has applications in many settings such as stock-cutting and scheduling. A straight-forward reduction from Partition shows that the problem cannot be approximated with a better absolute factor than 3/2. However, this reduction requires the numeric values to be exponentially large. In this paper, we present a (1.4+eps)-approximation algorithm with pseudo-polynomial running time. This implies that for polynomially bounded input data the problem can be approximated with a strictly better ratio than for exponential input which is a very rare phenomenon in combinatorial optimization.

Name(s):Andreas Wiese
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Andreas Wiese, 07/18/2016 12:52 PM
Last modified:
halma/MPII/DE, 10/18/2018 12:00 AM
  • Andreas Wiese, 07/18/2016 12:52 PM -- Created document.