1. bookVolume 29 (2021): Issue 3 (October 2021)
Journal Details
License
Format
Journal
eISSN
1898-9934
First Published
09 Jun 2008
Publication timeframe
4 times per year
Languages
English
access type Open Access

Algorithm NextFit for the Bin Packing Problem

Published Online: 30 Dec 2021
Volume & Issue: Volume 29 (2021) - Issue 3 (October 2021)
Page range: 141 - 151
Accepted: 30 Jun 2021
Journal Details
License
Format
Journal
eISSN
1898-9934
First Published
09 Jun 2008
Publication timeframe
4 times per year
Languages
English

Summary. The bin packing problem is a fundamental and important optimization problem in theoretical computer science [4], [6]. An instance is a sequence of items, each being of positive size at most one. The task is to place all the items into bins so that the total size of items in each bin is at most one and the number of bins that contain at least one item is minimum.

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

MSC

Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, Karol Pąk, and Josef Urban. Mizar: State-of-the-art and beyond. In Manfred Kerber, Jacques Carette, Cezary Kaliszyk, Florian Rabe, and Volker Sorge, editors, Intelligent Computer Mathematics, volume 9150 of Lecture Notes in Computer Science, pages 261–279. Springer International Publishing, 2015. ISBN 978-3-319-20614-1. doi:10.1007/978-3-319-20615-8_17.10.1007/978-3-319-20615-8_17Search in Google Scholar

Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, and Karol Pąk. The role of the Mizar Mathematical Library for interactive proof development in Mizar. Journal of Automated Reasoning, 61(1):9–32, 2018. doi:10.1007/s10817-017-9440-6.10.1007/s10817-017-9440-6604425130069070Search in Google Scholar

Noboru Endou. Double series and sums. Formalized Mathematics, 22(1):57–68, 2014. doi:10.2478/forma-2014-0006.10.2478/forma-2014-0006Search in Google Scholar

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. ISBN 0716710447.Search in Google Scholar

David S. Johnson. Near-optimal Bin Packing Algorithms. PhD thesis. Massachusetts Institute of Technology, 1973.Search in Google Scholar

B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer Publishing Company, Incorporated, 5th edition, 2012. ISBN 3642244874, 9783642244872.10.1007/978-3-642-24488-9Search in Google Scholar

Robert Milewski. Natural numbers. Formalized Mathematics, 7(1):19–22, 1998.Search in Google Scholar

Christoph Schwarzweller. Proth numbers. Formalized Mathematics, 22(2):111–118, 2014. doi:10.2478/forma-2014-0013.10.2478/forma-2014-0013Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo