@ARTICLE{BINPACK1.MIZ,
 AUTHOR = {Fujiwara, Hiroshi and Adachi, Ryota and Yamamoto, Hiroaki},
  TITLE = {Algorithm NextFit for the Bin Packing Problem},
  NOTE = {This work was supported by JSPS KAKENHI Grant Numbers
                  JP20K11689, JP20K11676, JP16K00033, JP17K00013,
                  JP20K11808, and JP17K00183.},
  ACKNOWLEDGEMENT = {We are very grateful to Prof. Yasunari Shidama
                  for his encouraging support.
                  We thank also Dr. Hiroyuki Okazaki
                  for helpful discussions.},
  SECTION1 = {Preliminaries},
  SECTION2 = {Optimal Packing},
  SECTION3 = {Online Algorithms},
  SECTION4 = {Feasibility of Algorithm NextFit},
  SECTION5 = {Approximation Guarantee of Algorithm NextFit},
  SECTION6 = {Tightness of Approximation Guarantee of Algorithm NextFit},
  DAY = {30},
  MONTH = {June},
  YEAR = {2021},
  ADDRESS1 = {Shinshu University\\Nagano, Japan},
  ADDRESS2 = {Intage Technosphere Inc.\\Tokyo, Japan},
  ADDRESS3 = {Shinshu University\\Nagano, Japan},
  KEYWORDS = {bin packing problem; online algorithm; approximation
                  algorithm; combinatorial optimization; theoretical
                  computer science},
  SUMMARY = {The bin packing problem is a fundamental and important optimization
  problem in theoretical computer
  science~\cite{Garey:1979:CIG:578533,KorteVygen}.  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.\par
  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~\cite{johnson1973near} 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.\par
  In this article, we formalize 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.}}

@book{Garey:1979:CIG:578533,
 author = {Garey, M. R. and Johnson, D. S.},
 title = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
 year = {1979},
 isbn = {0716710447},
 publisher = {W. H. Freeman \& Co.},
 address = {New York, NY, USA},
}

@book{Korte:2012:COT:2190621,
 author = {Korte, B. and Vygen, J.},
 title = {Combinatorial Optimization: Theory and Algorithms},
 year = {2012},
 isbn = {3642244874, 9783642244872},
 edition = {5th},
 publisher = {Springer Publishing Company, Incorporated},
}

@book{johnson1973near,
  title={Near-optimal Bin Packing Algorithms},
  author={Johnson, D. S.},
  series={PhD thesis},
  year={1973},
  publisher={Massachusetts Institute of Technology}
}
