科研之友
微信
新浪微博
Facebook
分享链接
摘要
A sequence of items that can be packed into m bins of unit size has to be assigned online to the bins minimizing the stretching factor, i.e., to stretch the bin sizes as little as possible such that the items fit into the bins. We present an elementary algorithm with stretching factor 11/7 improving the best known algorithm by Cheng et al. (2005) [5] with a stretching factor of 1.6. Our algorithm uses simple but efficient techniques of grouping the bins in batches of similar structure.
- 出版日期2013-7
