Two-Dimensional Knapsack for Circles

Autor(es)

Lintzmayer, Carla Negri ; Miyazawa, Flavio Keidi ; Xavier, Eduardo Candido ; Bender, MA ; FarachColton, M ; Mosteiro, MA

• Tipo de documento: Artigo Científico
• Fonte: LATIN 2018: THEORETICAL INFORMATICS; v. 10807, p. 14-pg., 2018-01-01.

Resumo

In this paper we consider the Two-dimensional Knapsack for Circles problem, in which we are given a set C of circles and want to pack a subset C' subset of C of them into a rectangular bin of dimensions w and h such that the sum of the area of circles in C' is maximum. By packing we mean that the circles do not overlap and they are fully contained inside the bin. We present a polynomial-time approximation scheme that, for any epsilon > 0, gives an approximation algorithm that packs a subset of the input circles into an augmented bin of dimensions w and (1 + O(epsilon)) h such that the area packed is at least (1 - O(epsilon)) times the area packed by an optimal solution into the regular bin of dimensions w and h. This result also extends to the multiple knapsack version of this problem. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções
• Beneficiário: Carla Negri Lintzmayer
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas
• Beneficiário: Rafael Crivellari Saliba Schouery
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, 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