Busca avançada
Ano de início
Entree


Techniques and results on approximation algorithms for packing circles

Texto completo
Autor(es):
Miyazawa, Flavio K. ; Wakabayashi, Yoshiko
Número total de Autores: 2
Tipo de documento: Artigo Científico
Fonte: SAO PAULO JOURNAL OF MATHEMATICAL SCIENCES; v. 16, n. 1, p. 31-pg., 2022-04-11.
Resumo

This survey provides an introductory guide to some techniques used in the design of approximation algorithms for circle packing problems. We address three such packing problems, in which the circles may have different sizes. They differ on the type of the recipient. We consider the classical bin packing and strip packing, and a variant called knapsack packing. Our aim is to discuss some techniques and basic algorithms to motivate the reader to investigate these and other related problems. We also present the ideas used on more elaborated algorithms, without going into details, and mention known results on these problems. (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/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