| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Sao Paulo, Inst Math & Stat, BR-05508 Sao Paulo - Brazil
[2] Univ Estadual Campinas, Inst Comp, BR-13081970 Campinas, SP - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE; v. 23, n. 3 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| FAPESP's process: | 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Research Grants - Young Investigators Grants |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings |
| Grantee: | Reinaldo Morabito Neto |
| Support Opportunities: | Research Projects - Thematic Grants |