MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

The optimal absolute ratio for online bin packing

Rob van Stee
University of Leicester
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 19 August 2014
13:00
30 Minutes
E1 4
024
Saarbrücken

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

Sebastian Ott
--email hidden
passcode not visible
logged in users only

Sebastian Ott, 08/18/2014 11:11
Sebastian Ott, 08/18/2014 11:10 -- Created document.