PTAS para Problema do Empacotamento de Soma Mínima com Quadrados

  • Rachel V. Saraiva UNICAMP
  • Rafael C. S. Schouery UNICAMP

Resumo


O trabalho trata do problema do empacotamento de soma mínima com itens quadrados, em que uma lista de itens quadrados deve ser empacotada em recipientes 1 × 1, e o custo de empacotar cada item é igual ao índice do recipiente em que é empacotado. O problema tem aplicações na minimização do tempo médio de operações logísticas como corte e entrega de produtos. Nesse trabalho apresentamos um esquema de aproximação (PTAS) para o problema.

Referências

Bansal, N., Correa, J. R., Kenyon, C., and Sviridenko, M. (2006). Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Mathematics of Operations Research, 31(1):31–49.

Eliiyi, U. and Eliiyi, D. T. (2009). Applications of bin packing models through the supply chain. International Journal of Business and Management Studies, 1(1):11–19.

Epstein, L., Johnson, D. S., and Levin, A. (2018). Min-sum bin packing. Journal of Combinatorial Optimization, 36(2):508–531.

Epstein, L. and Levin, A. (2007). Minimum weighted sum bin packing. In International Workshop on Approximation and Online Algorithms, pages 218–231.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
Publicado
06/08/2023
SARAIVA, Rachel V.; SCHOUERY, Rafael C. S.. PTAS para Problema do Empacotamento de Soma Mínima com Quadrados. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 124-128. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.230561.