Online Circle and Sphere Packing
Resumo
In the Online Circle Packing in Squares, circles arrive one at a time and we need to pack them into the minimum number of unit square bins. We improve the previous best-known competitive ratio for the bounded space version from 2.439 to 2.3536 and we also give an unbounded space algorithm. Our algorithms also apply to the Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes, for which no previous results were known.
Referências
Christensen, H. I., Khan, A., Pokutta, S., and Tetali, P. (2017). Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63–79.
Epstein, L. (2010). Two-dimensional Online Bin Packing with Rotation. Theoretical Computer Science, 411(31):2899–2911.
Hokama, P., Miyazawa, F. K., and Schouery, R. C. S. (2016). A Bounded Space Algorithm for Online Circle Packing. Information Processing Letters, 116(5):337–342.
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.
Specht, E. Packomania. [link]. Accessed: 2018-03-27.
Szabó, P. G., Markót, M. C., Csendes, T., Specht, E., Casado, L. G., and García, I. (2007). New Approaches to Circle Packing in a Square. Springer Optimization and Its Applications. Springer US, New York, USA.
Tatarevic, M. (2015). On Limits of Dense Packing of Equal Spheres in a Cube. The Electronic Journal of Combinatorics, 22(1):35.
Epstein, L. (2010). Two-dimensional Online Bin Packing with Rotation. Theoretical Computer Science, 411(31):2899–2911.
Hokama, P., Miyazawa, F. K., and Schouery, R. C. S. (2016). A Bounded Space Algorithm for Online Circle Packing. Information Processing Letters, 116(5):337–342.
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.
Specht, E. Packomania. [link]. Accessed: 2018-03-27.
Szabó, P. G., Markót, M. C., Csendes, T., Specht, E., Casado, L. G., and García, I. (2007). New Approaches to Circle Packing in a Square. Springer Optimization and Its Applications. Springer US, New York, USA.
Tatarevic, M. (2015). On Limits of Dense Packing of Equal Spheres in a Cube. The Electronic Journal of Combinatorics, 22(1):35.
Publicado
26/07/2018
Como Citar
LINTZMAYER, Carla Negri; MIYAZAWA, Flávio Keidi; XAVIER, Eduardo Candido.
Online Circle and Sphere Packing. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 65-68.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3158.
