Approximation algorithms have been intensively studied. Algorithm NextFit would be the simplest one. The algorithm repeatedly does the following: If the first unprocessed item in the sequence can be placed, in terms of size, additionally to the bin into which the algorithm has placed an item the last time, place the item into that bin; otherwise place the item into an empty bin. Johnson [5] proved that the number of the resulting bins by algorithm NextFit is less than twice the number of the fewest bins that are needed to contain all items.

In this article, we formalize in Mizar [1], [2] the bin packing problem as follows: An instance is a sequence of positive real numbers that are each at most one. The task is to find a function that maps the indices of the sequence to positive integers such that the sum of the subsequence for each of the inverse images is at most one and the size of the image is minimum. We then formalize algorithm NextFit, its feasibility, its approximation guarantee, and the tightness of the approximation guarantee.

#### Keywords

- bin packing problem
- online algorithm
- approximation algorithm
- combinatorial optimization

#### MSC

- 68W27
- 05B40
- 68V20

Duality Notions in Real Projective Plane Finite Dimensional Real Normed Spaces are Proper Metric Spaces Relationship between the Riemann and Lebesgue Integrals Improper Integral. Part I About Graph Sums Improper Integral. Part II Automatization of Ternary Boolean Algebras Prime Representing Polynomial Quadratic Extensions The 3-Fold Product Space of Real Normed Spaces and its Properties