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

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

DOI: https://doi.org/10.5753/etc.2023.230561

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.