1. Fast allocation algorithms
- Author
-
Dayid S. Johnson
- Subjects
Mathematical optimization ,Prediction algorithms ,Computer science ,Bin packing problem ,Approximation algorithm ,Algorithm design ,Multiprocessing ,Upper and lower bounds ,Algorithm ,Time complexity ,Scheduling (computing) - Abstract
In this paper we consider polynomial-time algorithms for bin packing and their applications. The previously studied FIRST FIT and BEST FIT algorithms are shown to be special cases of a more generalized class of algorithms which all have similar worst case behavior. Linear time algorithms are then introduced which, though "faster" than FIRST FIT and BEST FIT, have the same, or better, worst case behavior. Finally, an improved polynomial-time algorithm is found for a problem of scheduling on multiprocessing systems, by treating this as a bin packing problem.
- Published
- 1972