In the (1-dimensional) bin packing problem, we are asked to pack all the given items into bins, each of capacity one, so that the number of non-empty bins is minimized. Zhu [Chaos, Solitons & Fractals 2016] proposed an approximation algorithm MM that sorts the item sequence in a non-increasing order by size at the beginning, and then repeatedly packs, into the current single open bin, first as many of the largest items in the remaining sequence as possible and then as many of the smallest items in the remaining sequence as possible. In this paper we prove that the asymptotic approximation ratio of MM is at most 1.5. Next, focusing on the fact that MM is at the intersection of two algorithm classes, max-min algorithms and 1-bounded space algorithms, we comprehensively analyze the theoretical performance bounds of each subclass derived from the two classes. Our results include a lower bound of 1.25 for the intersection of the two classes. Furthermore, we extend the theoretical analysis over algorithm classes to the cardinality constrained bin packing problem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem

  • Hiroshi Fujiwara,
  • Rina Atsumi,
  • Hiroaki Yamamoto

摘要

In the (1-dimensional) bin packing problem, we are asked to pack all the given items into bins, each of capacity one, so that the number of non-empty bins is minimized. Zhu [Chaos, Solitons & Fractals 2016] proposed an approximation algorithm MM that sorts the item sequence in a non-increasing order by size at the beginning, and then repeatedly packs, into the current single open bin, first as many of the largest items in the remaining sequence as possible and then as many of the smallest items in the remaining sequence as possible. In this paper we prove that the asymptotic approximation ratio of MM is at most 1.5. Next, focusing on the fact that MM is at the intersection of two algorithm classes, max-min algorithms and 1-bounded space algorithms, we comprehensively analyze the theoretical performance bounds of each subclass derived from the two classes. Our results include a lower bound of 1.25 for the intersection of the two classes. Furthermore, we extend the theoretical analysis over algorithm classes to the cardinality constrained bin packing problem.