Beating the Harmonic Lower Bound for Online Bin Packing

Rob Van Stee

17th March 2016, 10:00 in ADR LG26

Abstract:
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 performance ratio of 1.5815, which constitutes the first improvement over the algorithm Harmonic++ in fifteen years and reduces the gap to the lower bound by roughly 15%. This algorithm achieved a competitive ratio of 1.58889 and is one instance of the Super Harmonic framework; a lower bound of Ramanan et al. shows that within this framework, no competitive ratio below 1.58333 can be achieved. We also give a lower bound of 1.5766 for variations of our algorithm.

Share this page:

Contact Us

Admissions Enquiries:
BSc: +44 (0) 116 252 5280
MSc: +44 (0) 116 252 2265
E: BSc  seadmissions@le.ac.uk
E: MSc  pgadmissions@le.ac.uk

Departmental Enquiries:
T: +44 (0) 116 252 2129/3887
F: +44 (0) 116 252 3604
E: csadmin@mcs.le.ac.uk

Dept of Informatics
University of Leicester
Leicester, LE1 7RH
United Kingdom

Accessibility

DisabledGo logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has a detailed accessibility guide for the Informatics Building.