1972 · 182 citations · 3 references
ComputingComputer ScienceComputer SystemsAlgorithmsOperations ResearchOptimizationAlgorithm AnalysisCombinatorial OptimizationHeuristic OptimizationHeuristic SearchResource AllocationSorting AlgorithmsHeuristic AlgorithmsHeuristic ApproachMemory AllocationMemory PlacementReal NumbersWorst-case BoundsWorst-case ComplexityWorst-case Optimization
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.
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*.
3
Samuel Eilon, Nicos Christofides · Management Science · 1971 · 166 citations
Natural Sciences, Industrial Engineering, Operations Management +7
Bounds on multiprocessing anomalies and related packing algorithms
Ronald Graham · 1971 · 110 citations · Full text