A tight lower bound for the online bounded space hypercube bin packing problem

Autor(es)

Kohayakawa, Yoshiharu ^[1] ; Miyazawa, Flavio Keidi ^[2] ; Wakabayashi, Yoshiko ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Math & Stat, BR-05508 Sao Paulo - Brazil

^[2] Univ Estadual Campinas, Inst Comp, BR-13081970 Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE; v. 23, n. 3 2021.
• Citações Web of Science: 0

Resumo

In the d-dimensional hypercube bin packing problem, a given list of d-dimensional hypercubes must be packed into the smallest number of hypercube bins. Epstein and van Stee {[}SIAM J. Comput. 35 (2005)] showed that the asymptotic performance ratio rho of the online bounded space variant 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), using probabilistic arguments. (AU)

• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
• 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: 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