Scholarlink

<p>We study two semi-online models for bin packing and exhibit them on cardinality constrained bin packing with small values of <i>k</i>. In this variant of the bin packing problem, each bin can have at most <i>k</i> items whose total size does not exceed 1. For the semi-online model where the algorithm may use a reordering buffer, we show that even if a single item can be stored in the buffer at any point in time, the best possible asymptotic competitive ratio for the case <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(k=2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> is smaller than that of the purely online problem. For the model with two parallel solutions, which is equivalent to the model with advice with a single bit of advice, we show an improved upper bound on the asymptotic competitive ratio for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(k=3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Semi-online models for cardinality constrained bin packing

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月4日

查看全文
  • Leah Epstein,
  • Asaf Levin

摘要

We study two semi-online models for bin packing and exhibit them on cardinality constrained bin packing with small values of k. In this variant of the bin packing problem, each bin can have at most k items whose total size does not exceed 1. For the semi-online model where the algorithm may use a reordering buffer, we show that even if a single item can be stored in the buffer at any point in time, the best possible asymptotic competitive ratio for the case \(k=2\) k = 2 is smaller than that of the purely online problem. For the model with two parallel solutions, which is equivalent to the model with advice with a single bit of advice, we show an improved upper bound on the asymptotic competitive ratio for \(k=3\) k = 3 .