Probabilistic analysis of algorithms for dual bin packing problems
作者： J Csirik , J.B.G Frenk , G Galambos , A.H.G Rinnooy Kan
DOI: 10.1016/0196-6774(91)90001-F
关键词: Combinatorics 、 Algorithm 、 Bin 、 Probabilistic analysis of algorithms 、 Renewal theory 、 Mathematics 、 Bin packing problem
摘要: In the dual bin packing problem, objective is to assign items of given size largest possible number bins, subject constraint that total assigned any at least equal 1. We carry out a probabilistic analysis this problem under assumption are drawn independently from uniform distribution on [0, 1] and reveal connection between classical as well renewal theory.
elsevier.com
sci-hub.se 参考文章(10)
Walter Knödel, A Bin Packing Algorithm with Complexity O(n log n) and Performance 1 in the Stochastic Limit mathematical foundations of computer science. pp. 369- 378 ,(1981) , 10.1007/3-540-10856-4_104
Kai Lai Chung, A Course in Probability Theory ,(1949)
Jbg Hans Frenk, On Banach algebras, renewal measures and regenerative processes ,(1987)
S.F Assmann, D.S Johnson, D.J Kleitman, J.Y.-T Leung, On a dual version of the one-dimensional bin packing problem Journal of Algorithms. ,vol. 5, pp. 502- 525 ,(1984) , 10.1016/0196-6774(84)90004-X
Jbg Hans Frenk, On a pairing heuristic in binpacking Memorandum COSOR. ,vol. 8613, ,(1986)
Antoine-S. Bailly, Science régionale - Walter Isard, Introduction to régional science. Englewood Cliffs (NJ), Prentice-Hall, 1975 L'Espace géographique. ,vol. 4, pp. 278- 278 ,(1975)
William Feller, An introduction to probability theory and its applications ,(1950)
Susan Fera. Assmann, Problems in discrete applied mathematics Massachusetts Institute of Technology. ,(1983)
George S. Lueker, An average-case analysis of bin packing with uniformly distributed item sizes ,(1982)
Erhan Çınlar, Introduction to Stochastic Processes ,(1974)