Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/237949
Type: Artigo
Title: A bounded space algorithm for online circle packing
Author: Hokama, Pedro
Miyazawa, Flávio K.
Schouery, Rafael C. S.
Abstract: We study the Online Circle Packing Problem where we need to pack circles that arrive online in square bins with the objective to minimize the number of bins used. An online algorithm is said to have bounded space if at any given time, only a constant number of bins are open, circles are packed only in open bins and once a bin is closed it cannot be reopened. In particular, we present a 2.4394-competitive bounded space algorithm for this problem and a 2.2920 lower bound on the competitive ratio of any online bounded space algorithm for this problem. © 2015 Elsevier B.V. All rights reserved.
We study the Online Circle Packing Problem where we need to pack circles that arrive online in square bins with the objective to minimize the number of bins used. An online algorithm is said to have bounded space if at any given time, only a constant numb
Subject: Geometria computacional
Algoritmos on-line
Empacotamento de círculos
Country: Holanda
Editor: Elsevier
Citation: Information Processing Letters. Elsevier, v. 116, n. 5, p. 337 - 342, 2016.
Rights: fechado
fechado
Identifier DOI: 10.1016/j.ipl.2015.12.007
Address: https://www.sciencedirect.com/science/article/pii/S0020019015002240
Date Issue: 2016
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
2-s2.0-84954286093.pdf360.55 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.