| Texto completo | |
| Autor(es): |
Kohayakawa, Yoshiharu
;
Miyazawa, Flavio Keidi
;
Wakabayashi, Yoshiko
;
Bender, MA
;
FarachColton, M
;
Mosteiro, MA
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | LATIN 2018: THEORETICAL INFORMATICS; v. 10807, p. 15-pg., 2018-01-01. |
| Resumo | |
We prove a tight lower bound on the asymptotic performance ratio. of the bounded space online d-hypercube bin packing problem, solving an open question raised in 2005. In the classic d-hypercube bin packing problem, we are given a sequence of d-dimensional hypercubes and we have an unlimited number of bins, each of which is a d-dimensional unit hypercube. The goal is to pack (orthogonally) the given hypercubes into the minimum possible number of bins, in such a way that no two hypercubes in the same bin overlap. The bounded space online d-hypercube bin packing problem is a variant of the d-hypercube bin packing problem, in which the hypercubes arrive online and each one must be packed in an open bin without the knowledge of the next hypercubes. Moreover, at each moment, only a constant number of open bins are allowed (whenever a new bin is used, it is considered open, and it remains so until it is considered closed, in which case, it is not allowed to accept new hypercubes). Epstein and van Stee (SIAM J Comput 35(2): 431-448, 2005) showed that rho is Omega(log d) and O(d/log d), and conjectured that it is Theta(log d). We show that rho is in fact Theta(d/log d). To obtain this result, we elaborate on some ideas presented by those authors, and go one step further showing how to obtain better (offline) packings of certain special instances for which one knows how many bins any bounded space algorithm has to use. Our main contribution establishes the existence of such packings, for large enough d, using probabilistic arguments. Such packings also lead to lower bounds for the prices of anarchy of the selfish d-hypercube bin packing game. We present a lower bound of Omega(d/log d) for the pure price of anarchy of this game, and we also give a lower bound of Omega(log d) for its strong price of anarchy. (AU) | |
| Processo FAPESP: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| 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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat |
| Beneficiário: | Oswaldo Baffa Filho |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |
| Processo FAPESP: | 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas |
| Beneficiário: | Rafael Crivellari Saliba Schouery |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |
| 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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |