REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU

Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: `http://hdl.handle.net/11320/12391`
 Tytuł: Algorithm NextFit for the Bin Packing Problem Autorzy: Fujiwara, HiroshiAdachi, RyotaYamamoto, Hiroaki Słowa kluczowe: bin packing problemonline algorithmapproximation algorithmcombinatorial optimization Data wydania: 2021 Data dodania: 4-sty-2022 Wydawca: DeGruyter Open Źródło: Formalized Mathematics, Volume 29, Issue 3, Pages 141-151 Abstrakt: 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. Afiliacja: Hiroshi Fujiwara - Shinshu University, Nagano, JapanRyota Adachi - Intage Technosphere Inc., Tokyo, JapanHiroaki Yamamoto - Shinshu University, Nagano, Japan Opis: This work was supported by JSPS KAKENHI Grant Numbers JP20K11689, JP20K11676, JP16K00033, JP17K00013, JP20K11808, and JP17K00183. URI: http://hdl.handle.net/11320/12391 DOI: 10.2478/forma-2021-0014 ISSN: 1426–2630 e-ISSN: 1898-9934 Typ Dokumentu: Article Właściciel praw: © 2021 University of BiałymstokuCC-BY-SA License ver. 3.0 or later Występuje w kolekcji(ach): Formalized Mathematics, 2021, Volume 29, Issue 3

Pliki w tej pozycji:
Plik Opis RozmiarFormat