Um QPTAS para o Problema de Empacotamento de Círculos em Linha
Resumo
No problema de empacotamento de círculos em linha, é dada uma lista de círculos que devem ser dispostos lado a lado sobre uma linha horizontal, de forma que cada círculo toque a linha somente em seu ponto mais baixo. O objetivo é minimizar a distância entre os pontos mais à esquerda e mais à direita dos círculos que definem os extremos do empacotamento. Em 2018, [Dürr et al. 2018] mostraram um QPTAS para o caso em que os itens são triângulos retângulos isósceles. Neste texto, apresentamos uma adaptação desse QPTAS para o problema de empacotamento de círculos em linha.Referências
Alt, H., Buchin, K., Chaplick, S., Cheong, O., Kindermann, P., Knauer, C., and Stehn, F. (2018). Placing your coins on a shelf. Journal of Computational Geometry, 9:312–327.
Cohn, H., Kumar, A., Miller, S., Radchenko, D., and Viazovska, M. (2017). The sphere packing problem in dimension 24. Annals of Mathematics, 185(3).
Dell’Arriva, E. (2021). In-line packing of circles. Master’s thesis, Universidade Estadual de Campinas.
Dürr, C., Hanzálek, Z., Konrad, C., Seddik, Y., Sitters, R., Óscar C. Vásquez, and Woeginger, G. (2018). The triangle scheduling problem. Journal of Scheduling, 21:305–312.
Hales, T. and Ferguson, S. (2006). A formulation of the kepler conjecture. Discrete & Computational Geometry, 36:21–69.
Kepler, J. (1611). Strena seu de nive sexangula (the six-cornered snowflake).
Miyazawa, F. K., Pedrosa, L. L. C., Schouery, R. C. S., Sviridenko, M., and Wakabayashi, Y. (2016). Polynomial-time approximation schemes for circle and other packing problems. Algorithmica, 76(2):536–568.
Miyazawa, F. K. and Wakabayashi, Y. (2022). Techniques and results on approximation algorithms for packing circles. São Paulo Journal of Mathematical Sciences, 16(1):585–615.
Viazovska, M. (2017). The sphere packing problem in dimension 8. Annals of Mathematics, 185(3).
Cohn, H., Kumar, A., Miller, S., Radchenko, D., and Viazovska, M. (2017). The sphere packing problem in dimension 24. Annals of Mathematics, 185(3).
Dell’Arriva, E. (2021). In-line packing of circles. Master’s thesis, Universidade Estadual de Campinas.
Dürr, C., Hanzálek, Z., Konrad, C., Seddik, Y., Sitters, R., Óscar C. Vásquez, and Woeginger, G. (2018). The triangle scheduling problem. Journal of Scheduling, 21:305–312.
Hales, T. and Ferguson, S. (2006). A formulation of the kepler conjecture. Discrete & Computational Geometry, 36:21–69.
Kepler, J. (1611). Strena seu de nive sexangula (the six-cornered snowflake).
Miyazawa, F. K., Pedrosa, L. L. C., Schouery, R. C. S., Sviridenko, M., and Wakabayashi, Y. (2016). Polynomial-time approximation schemes for circle and other packing problems. Algorithmica, 76(2):536–568.
Miyazawa, F. K. and Wakabayashi, Y. (2022). Techniques and results on approximation algorithms for packing circles. São Paulo Journal of Mathematical Sciences, 16(1):585–615.
Viazovska, M. (2017). The sphere packing problem in dimension 8. Annals of Mathematics, 185(3).
Publicado
06/08/2023
Como Citar
DELL’ARRIVA, Elisa; MIYAZAWA, Flávio K..
Um QPTAS para o Problema de Empacotamento de Círculos em Linha. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 114-118.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230684.
