Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
作者： Carsten Fischer , Heiko Röglin
DOI: 10.1007/978-3-662-49529-2_35
关键词:
摘要: In the bin covering problem, goal is to fill as many bins possible up a certain minimal level with given set of items different sizes. Online variants, in which arrive one after another and have be packed immediately on their arrival without knowledge about future items, been studied extensively literature. We study simplest online algorithm Dual Next-Fit, packs all arriving into same until it filled then proceeds next manner. The competitive ratio this any other reasonable 1 / 2.
springer.com
harvard.edu
sci-hub.st 参考文章(15)
David A. Levin, Elizabeth L. Wilmer, Y. Peres, Y. Peres, Y. Peres, Markov Chains and Mixing Times ,(2008)
Gary Lorden, On Excess Over the Boundary Annals of Mathematical Statistics. ,vol. 41, pp. 520- 527 ,(1970) , 10.1214/AOMS/1177697092
Janos Csirik, Claire Kenyon, David S. Johnson, Better approximation algorithms for bin covering symposium on discrete algorithms. pp. 557- 566 ,(2001) , 10.5555/365411.365533
J. Csirik, V. Totik, Online algorithms for a dual version of bin packing Discrete Applied Mathematics. ,vol. 21, pp. 163- 167 ,(1988) , 10.1016/0166-218X(88)90052-2
Nir Naaman, Raphael Rom, Average Case Analysis of Bounded Space Bin Packing Algorithms Algorithmica. ,vol. 50, pp. 72- 97 ,(2008) , 10.1007/S00453-007-9073-Y
Klaus Jansen, Roberto Solis-Oba, An asymptotic fully polynomial time approximation scheme for bin covering Theoretical Computer Science. ,vol. 306, pp. 543- 551 ,(2003) , 10.1016/S0304-3975(03)00363-3
Claire Kenyon, Best-fit bin-packing with random order symposium on discrete algorithms. pp. 359- 364 ,(1996) , 10.5555/313852.314083
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
Edward G. Coffman, János Csirik, Lajos Rónyai, Ambrus Zsbán, Random-order bin packing Discrete Applied Mathematics. ,vol. 156, pp. 2810- 2816 ,(2008) , 10.1016/J.DAM.2007.11.004
Eyjolfur Ingi Asgeirsson, Cliff Stein, None, Bounded-space online bin cover Journal of Scheduling. ,vol. 12, pp. 461- 474 ,(2009) , 10.1007/S10951-009-0116-X