Name
Abstract | ||
|---|---|---|
Abstract We consider the d-dimensional cube packing problem (d -CPP): given a list L of d -dimensional cubes and (an unlimited quantity of) d -dimensional unit-capacity cubes, called bins , find a packing of L into the minimum number of bins. We present two approximations algorithms for d -CPP, for fixed d. The first algorithm has an asymptotic performance bound that can be made arbitrarily close to 2 — 1/2 d . The second algorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarily close to 2 - (2/3) d . To our knowledge, these results improve the bounds known so far for d = 2 and d = 3, and are the first results with bounds that are not exponential in the dimension. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S1571-0653(04)00237-9 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Approximation algorithms,Multidimensional bin packing,Asymptotic performance | Discrete mathematics,Approximation algorithm,Combinatorics,Exponential function,Packing problems,Multidimensional analysis,Mathematics,Bin packing problem,Cube | Journal |
Volume | Issue | ISSN |
7 | 3 | Electronic Notes in Discrete Mathematics |
Citations | PageRank | References |
7 | 0.69 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshiharu Kohayakawa | 1 | 172 | 22.74 |
| F.K. Miyazawa | 2 | 7 | 0.69 |
| Prabhakar Raghavan | 3 | 13351 | 2776.61 |
| Y. Wakabayashi | 4 | 140 | 16.33 |