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:The optimal absolute ratio for online bin packing
Speaker:Rob van Stee
coming from:University of Leicester
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 19 August 2014
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
Abstract
In the online bin packing problem, a sequence of items with sizes in the interval (0,1] arrive one by one and need to be packed into bins, so that each bin contains items of total size at most 1. Each item must be irrevocably assigned to a bin before the next item becomes available. The algorithm has no knowledge about future items.

There is an unlimited supply of bins available, and the goal is to
minimize the total number of used bins (bins that receive at least one
item). We present an online bin packing algorithm with absolute
competitive ratio 5/3, which is optimal.

Contact
Name(s):Sebastian Ott
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Sebastian Ott, 08/18/2014 11:11 AM
  • Sebastian Ott, 08/18/2014 11:10 AM -- Created document.