Name
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 approximation 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 |
|---|---|---|
2004 | 10.1007/s00453-004-1102-5 | ALGORITHMICA |
Keywords | Field | DocType |
approximation algorithms,multidimensional bin packing,asymptotic performance | Discrete mathematics,Approximation algorithm,Combinatorics,Exponential function,Packing problems,Square packing in a square,Klee–Minty cube,Mathematics,Cube | Journal |
Volume | Issue | ISSN |
40.0 | 3 | 0178-4617 |
Citations | PageRank | References |
14 | 1.11 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshiharu Kohayakawa | 1 | 477 | 64.87 |
| Flávio Keidi Miyazawa | 2 | 215 | 21.95 |
| Prabhakar Raghavan | 3 | 13351 | 2776.61 |
| Yoshiko Wakabayashi | 4 | 268 | 31.75 |