Worst-case analysis of memory allocation algorithms

TLDR

Memory allocation problems can be modeled as a bin‑packing problem where real numbers in (0,1] must be placed into the fewest bins without exceeding capacity 1. The study seeks to identify effective heuristic methods for bin assignment, since computing the optimal number of bins is impractical. Four simple heuristics are examined, and their worst‑case performance is tightly bounded by comparing the number of bins they use to the optimal quantity.

Abstract

Various memory allocation problems can be modeled by the following abstract problem. Given a list A = (α1,α2,...αn,) of real numbers in the range (0, 1], place these in a minimum number of “bins” so that no bin holds numbers summing to more than 1. We let A* be the smallest number of bins into which the numbers of list A may be placed. Since a general placement algorithm for attaining A* appears to be impractical, it is important to determine good heuristic methods for assigning numbers of bins. We consider four such simple methods and analyze the worst-case performance of each, closely bounding the maximum of the ratio of the number of bins used by each method applied to list A to the optimal quantity A*.