Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

A bounded space algorithm for online circle packing

Texto completo
Autor(es):
Hokama, Pedro [1] ; Miyazawa, Flavio K. [1] ; Schouery, Rafael C. S. [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Av Albert Einstein, 1251 Cidade Univ, BR-13083852 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: INFORMATION PROCESSING LETTERS; v. 116, n. 5, p. 337-342, MAY 2016.
Citações Web of Science: 6
Resumo

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. (C) 2015 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 11/13382-3 - Problema de roteamento de veículos com restrições práticas
Beneficiário:Pedro Henrique Del Bianco Hokama
Modalidade de apoio: Bolsas no Brasil - Doutorado
Processo FAPESP: 13/21744-8 - Abordagens Teóricas e Práticas para Problemas de Empacotamento
Beneficiário:Rafael Crivellari Saliba Schouery
Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado