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

Abstract

This work discuss the min-sum bin packing problem with square items, where a list of square items has to be packed into bins of dimension 1×1, and the cost of packing each item is equal to the index of the bin it is placed in. The problem has applications in minimizing the average time of logistic operations such as cutting stock and delivery of products. In this paper we present an approximation scheme (PTAS) for the problem.

References

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.