Campus Event Calendar
Event Entry
What and Who
A (5/3+epsilon)-approximation for strip packing
Rob van Stee
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 2 August 2011
13:00
30 Minutes
E1 4
021
Saarbrücken
Abstract
We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width 1 and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of 5/3+eps for any eps>0. This result significantly narrows the gap between the best known upper bound of 1.9396 by Harren and van Stee and the lower bound 3/2.
Contact
Rob van Stee
--email hidden
passcode not visible
logged in users only
Rob van Stee, 07/21/2011 17:14 -- Created document.