Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems
作者： Mingen Lin , Yang Yang , Jinhui Xu
DOI: 10.1007/11940128_57
关键词:
摘要: In this paper, we study two variants of the bin packing /covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Covering (LBC) problems, present new approximation algorithms for each them. For offline MRBP problem, previous best known ratio is $\frac{6}{5}=1.2$, achieved by classical First-Fit-Increasing (FFI) algorithm [1]. give a FFI-type with an $\frac{80}{71}\approx 1.12676$. LBC it has been shown in [2] that First-Fit-Decreasing (FFD) achieves $\frac{71}{60}\approx 1.18333$. FFD-type $\frac{17}{15}\approx 1.13333$. Both are simple, run near linear time (i.e., O(n logn)), therefore practical.
springer.com
springerlink.com参考文章(13)
Joan Boyar, Leah Epstein, Lene M Favrholdt, Jens S Kohrt, Kim S Larsen, Morten Monrad Pedersen, Sanne Wøhlk, None, The maximum resource bin packing problem fundamentals of computation theory. pp. 397- 408 ,(2005) , 10.1007/11537311_35
Mingen Lin, Yang Yang, Jinhui Xu, On lazy bin covering and packing problems computing and combinatorics conference. pp. 340- 349 ,(2006) , 10.1007/11809678_36
G. Galambos, G. J. Woeginger, Repacking helps in bounded space on-line bind-packing Computing. ,vol. 49, pp. 329- 338 ,(1993) , 10.1007/BF02248693
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
H. Shachnai, T. Tamir, On Two Class-Constrained Versions of the Multiple Knapsack Problem Algorithmica. ,vol. 29, pp. 442- 467 ,(2001) , 10.1007/S004530010057
David S Johnson, Michael R Garey, A 7160 theorem for bin packing Journal of Complexity. ,vol. 1, pp. 65- 106 ,(1985) , 10.1016/0885-064X(85)90022-6
Richard E. Ladner, Tami Tamir, Amotz Bar-Noy, Windows scheduling as a restricted version of Bin Packing symposium on discrete algorithms. pp. 224- 233 ,(2004) , 10.5555/982792.982824
Donald K. Friesen, Michael A. Langston, Analysis of a compound bin packing algorithm SIAM Journal on Discrete Mathematics. ,vol. 4, pp. 61- 79 ,(1991) , 10.1137/0404007
M.R Garey, R.L Graham, D.S Johnson, Andrew Chi-Chih Yao, Resource constrained scheduling as generalized bin packing Journal of Combinatorial Theory, Series A. ,vol. 21, pp. 257- 298 ,(1976) , 10.1016/0097-3165(76)90001-7
J. Csirik, The parametric behavior of the first-fit decreasing bin packing algorithm Journal of Algorithms. ,vol. 15, pp. 1- 28 ,(1993) , 10.1006/JAGM.1993.1028