Palavras-chave
Approximation
Optimization
Como Citar
Resumo
The Bin Packing Problem is a classical NP-hard problem. This study gathers the proofs of the approximation ratios for several known approximation algorithms for this problem, including Next-Fit, First-Fit, and two approximation schemes. It also considers the inapproximability of the Bin Packing Problem by ratios lower than 1.5, and lower bounds for the competitive ratios of online algorithms, bounded-space and otherwise.
Referências
SIMCHI-LEVI, D. New worst-case results for the bin-packing problem.c2006.
YAO, A. C.-C. New algorithms for bin packing. J. ACM, New York, NY, USA, v. 27, n. 2, p. 207–227, Apr. 1980.
LEE, C. C.; LEE, D. T. A simple on-line bin-packing algorithm. J. ACM, New York, NY, USA, v. 32, n. 3, p. 562–572, July 1985.
JOHNSON, D. S. Fast algorithms for bin packing. Journal of Computer and System Sciences, v. 8, n. 3, p. 272 – 314, 1974.
JOHNSON, D. S.; ULLMAN, J. D.; GAREYI, M. R.; GRAHAMII, R. L.Worst-case performance bounds for simple one-dimensional packing algorithms*.
JOHNSON, D. S. Near-optimal bin packing algorithms. 1973. PhD thesis - Massachusetts Institute of Technology, 1973.
FERNANDEZ DE LA VEGA, W.; LUEKER, G. S. Bin packing can be solved within 1 + ε in linear time. Combinatorica, v. 1, n. 4, p. 349–355, Dec1981.
KARMARKAR, N.; KARP, R. M. An efficient approximation scheme for the one-dimensional bin-packing problem. SFCS ’82. Washington, DC, USA: IEEE Computer Society, c1982. p. 312–320.
Todos os trabalhos são de acesso livre, sendo que a detenção dos direitos concedidos aos trabalhos são de propriedade da Revista dos Trabalhos de Iniciação Científica da UNICAMP.