An approximation algorithm for square packing |
| |
| Authors: | Rob van Stee |
| |
| Affiliation: | Centre for Mathematics and Computer Science (CWI), Kruislaan 413, NL-1098 SJ Amsterdam, The Netherlands |
| |
| Abstract: | We consider the problem of packing squares into bins which are unit squares, where the goal is to minimize the number of bins used. We present an algorithm for this problem with an absolute worst-case ratio of 2, which is optimal provided P≠NP. |
| |
| Keywords: | Bin packing Square packing Approximation algorithm Absolute worst-case ratio |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
