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:Improvements in online bin packing
Speaker:Sandy Heydrich
coming from:Max-Planck-Institut f├╝r Informatik - D1
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
Date, Time and Location
Date:Tuesday, 2 February 2016
Duration:30 Minutes
Building:E1 4
In the online bin packing problem, items of sizes in (0,1] arrive online to be packed into bins of size 1. The goal is to minimize the number of used bins. In this paper, we present an online bin packing algorithm with asymptotic competitive ratio of 1.5817, which constitutes the first improvement over the algorithm Harmonic++ in fifteen years. This algorithm achieved a competitive ratio of 1.58889 and is one instance of the SuperHarmonic framework; a lower bound of Ramanan et al. shows that within this framework, no competitive ratio below 1.58333 can be achieved.

We make two crucial changes to that framework. First, some of the decisions of the algorithm will depend on exact sizes of items, instead of their rough sizes (called types), as done in SuperHarmonic. Furthermore, SuperHarmonic assigns items colors to control the packing process. In our framework, we postpone the coloring decision in order to be able to bound the number of bins where the optimal solution performs significantly better than our algorithm.

Finally, the analysis of our algorithm requires an additional step of marking items, which results in additional constraints in the linear program that describes the competitive ratio of the algorithm. We then solve this LP with the ellipsoid method, making use of a separation oracle.

In addition, we give a lower bound of 1.5766 for algorithms in our framework. This shows that fundamentally different ideas will be required to make further improvements.

Name(s):Sandy Heydrich
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Sandy Heydrich, 01/20/2016 08:27 AM -- Created document.