Scholarlink

The survey presents an overview of approximation algorithms for the classical bin packing problem and reviews the more important results on performance guarantees. Both on-line and off-line algorithms are analyzed. The investigation is extended to variants of the problem through an extensive review of dual versions, variations on bin sizes, and item packing, as well as those produced by additional constraints. The bin packing papers are classified according to a four-field classification scheme that allows one to create a compact synthesis of the topic, the main results, and the corresponding algorithms.

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

An Updated Overview of Bin Packing Approximation Algorithms

  • 动态工具书词条

  • 发表日期：

    2025年

查看全文
  • Gábor Galambos,
  • Silvano Martello,
  • Daniele Vigo

摘要

The survey presents an overview of approximation algorithms for the classical bin packing problem and reviews the more important results on performance guarantees. Both on-line and off-line algorithms are analyzed. The investigation is extended to variants of the problem through an extensive review of dual versions, variations on bin sizes, and item packing, as well as those produced by additional constraints. The bin packing papers are classified according to a four-field classification scheme that allows one to create a compact synthesis of the topic, the main results, and the corresponding algorithms.