A 17/10-approximation algorithm fork-bounded space on-line variable-sized bin packing |
| |
Authors: | Zhang Guochuan |
| |
Affiliation: | (1) Institute of Advanced Mathematics, Zhejiang University, 310027 Hangzhou, China |
| |
Abstract: | A version of thek-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 fork≥3. This research is supported by the Science Foundation under State Education Committee of China. The earlier version was done in Institute of Applied Mathematics, Academia Sinica. |
| |
Keywords: | Bin packing on-line algorithm worst-case analysis |
本文献已被 SpringerLink 等数据库收录! |
|