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.)

Online circle and sphere packing

Texto completo
Autor(es):
Lintzmayer, Carla Negri [1] ; Miyazawa, Flavio Keidi [2] ; Xavier, Eduardo Candido [2]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre - Brazil
[2] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: THEORETICAL COMPUTER SCIENCE; v. 776, p. 75-94, JUL 12 2019.
Citações Web of Science: 0
Resumo

In this paper we consider the Online Bin Packing Problem in three variants: Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes. The two first ones receive an online sequence of circles (items) of different radii while the third one receives an online sequence of spheres (items) of different radii, and they want to pack the items into the minimum number of unit squares, isosceles right triangles of leg length one, and unit cubes, respectively. For Online Circle Packing in Squares, we improve the previous best-known competitive ratio for the bounded space version, when at most a constant number of bins can be open at any given time, from 2.439 to 2.3536. For Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes we show bounded space algorithms of asymptotic competitive ratios 2.5490 and 3.5316, respectively, as well as lower bounds of 2.1193 and 2.7707 on the competitive ratio of any online bounded space algorithm for these two problems. We also considered the online unbounded space right variant of these three problems which admits a small reorganization of the items inside some of the bins after their packing, and we present algorithms of competitive ratios 2.3105, 2.5094, and 3.5146 for Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes, respectively. Throughout the text, we also discuss how our algorithms can be extended to other problems. (C) 2019 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 16/23552-7 - Problemas de corte e empacotamento: abordagens práticas e teóricas
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Auxílio à Pesquisa - Regular
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
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
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
Linha de fomento: Auxílio à Pesquisa - Temático