4 - Bin-Packing

Summary

Introduction

In this chapter, we consider a very basic packing problem, called bin-packing, where the objective is to pack items with different weights or sizes in boxes or bins of fixed capacity using as few bins as possible. In particular, assuming that the capacity of each bin is 1 and the weight of each item is at most 1, the problem is to divide the set of items into as few partitions (corresponding to individual bins) as possible, such that the sum of the weight of items in each partition is at most 1. The offline problem when the full set of items is available ahead of time is known to be NP-hard.

Applications of the bin-packing problem in both offline and online settings include inventory management where pellets or containers need to be packed with objects of different sizes and weights, subject to a size or weight capacity, job scheduling where each server can process jobs subject to a maximum capacity, and storing large data sets on disks of finite size, and many others.

Bin-packing is one of the most well-studied problems in the area of online algorithms for which multiple classes of algorithms have been studied. In this chapter, we review two such classes: AnyFit algorithms that try to fit an item in a bin using some local rule and (ii) the Harmonic algorithm that creates special classes of bins ahead of time and assigns an item to a bin of a particular class. The philosophy behind these two classes of algorithms is entirely different; however, they result in very similar competitive ratios when the number of items is large.

We show that with a large number of items, the competitive ratio of AnyFit class of algorithms is 1.7, while the competitive ratio of the Harmonic algorithm is 1.691, where both the ratios are tight. We also show that for arbitrarily many number of items, the lower bound on the competitive ratio of any deterministic online algorithm is 5/3.

Problem Formulation

Consider that there is an infinite supply of bins each with a capacity 1. Items with weight wi arrive sequentially that have to be placed in one of the bins (subject to the sum-weight of the items placed in any bin being less than its capacity) irrevocably with an objective of minimizing the number of bins used.