arbiter
JournalsPricingAccount

Semi-online models for cardinality constrained bin packing

Leah Epstein & Asaf Levin

Journal of Scheduling2025https://doi.org/10.1007/s10951-025-00854-zarticle
AJG 1ABDC B
Weight
0.37

What the paper says

Abstract 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> .

1 citation

Open paper page →

Cite this paper

https://doi.org/https://doi.org/10.1007/s10951-025-00854-z

Or copy a formatted citation

@article{leah2025,
  title        = {{Semi-online models for cardinality constrained bin packing}},
  author       = {Leah Epstein & Asaf Levin},
  journal      = {Journal of Scheduling},
  year         = {2025},
  doi          = {https://doi.org/https://doi.org/10.1007/s10951-025-00854-z},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

Semi-online models for cardinality constrained bin packing

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.37

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.16 × 0.4 = 0.06
M · momentum0.53 × 0.15 = 0.08
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.