Next-fit packs a list and its reverse into the same number of bins
作者： David C Fisher
DOI: 10.1016/0167-6377(88)90060-0
关键词:
摘要: Suppose the next-fit algorithm packs {x"1, x"2, ..., x"n} into k identical bins. Under modest assumptions about what fits a bin, we prove that also {x"n, x"1} Thus, decreasing uses same number of bins as increasing algorithm.
elsevier.com
sci-hub.se 参考文章(7)
F. R. K. Chung, M. R. Garey, D. S. Johnson, On Packing Two-Dimensional Bins Siam Journal on Algebraic and Discrete Methods. ,vol. 3, pp. 66- 76 ,(1982) , 10.1137/0603007
Brenda S Baker, Edward G Coffman, Jr, A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing Siam Journal on Algebraic and Discrete Methods. ,vol. 2, pp. 147- 152 ,(1981) , 10.1137/0602019
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Micha Hofri, Sami Kamhi, A stochastic analysis of the NFD bin-packing algorithm Journal of Algorithms. ,vol. 7, pp. 489- 509 ,(1986) , 10.1016/0196-6774(86)90015-5
WanSoo T. Rhee, Probabilistic analysis of the next fit decreasing algorithm for bin-packing Operations Research Letters. ,vol. 6, pp. 189- 191 ,(1987) , 10.1016/0167-6377(87)90018-6
J. Csirik, G. Galambos, J.B.G. Frenk, A.M. Frieze, A.H.G. Rinnooy Kan, A probabilistic analysis of the next fit decreasing bin packing heuristic Operations Research Letters. ,vol. 5, pp. 233- 236 ,(1986) , 10.1016/0167-6377(86)90013-1