Approximation Schemes Under Resource Augmentation for Knapsack and Packing Problems of Hyperspheres and Other Shapes

Autor(es)

Chagas, Vitor Gomes ; Dell'Arriva, Elisa ; Miyazawa, Flavio Keidi

• Tipo de documento: Artigo Científico
• Fonte: APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2023; v. 14297, p. 15-pg., 2023-01-01.

Resumo

The problems we investigate consist in packing hyperspheres in bins optimizing some resource, such as minimizing the number or the size of the bins, or maximizing the total profit associated with the packed items. We present an approximation scheme under resource augmentation for the circle knapsack problem, i.e., a polynomial-time algorithm that, for any constant epsilon > 0, obtains a solution whose value is within a factor of 1 - epsilon of the optimal value, using augmented bins of height increased by a factor of e. To the best of our knowledge, this is the first approximation scheme for this problem. Additionally, our technique can be extended to accomplish PTASs for other packing problems, like the multiple strip packing problem and the problem of minimizing the size of the bins. Our technique is not restricted to circles and hyperspheres, working for items, bins and strip bases of different convex shapes, such as squares, regular polygons with bounded number of sides, ellipses, among others, and for their generalizations to the d-dimensional case, for constant d. (AU)

• Processo FAPESP: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático