Open-end bin packing: new and old analysis approaches
From MaRDI portal
Publication:2172402
DOI10.1016/J.DAM.2022.07.003zbMATH Open1500.90056arXiv2105.05923OpenAlexW3161015378MaRDI QIDQ2172402FDOQ2172402
Authors: Leah Epstein 
Publication date: 15 September 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: We analyze a recently introduced concept, called the price of clustering, for variants of bin packing called open-end bin packing problems (OEBP). Input items have sizes, and they also belong to a certain number of types. The new concept deals with the comparison of optimal solutions for the cases where items of distinct types can and cannot be packed together, respectively. The problem is related to greedy bin packing algorithms and to batched bin packing, and we discuss some of those concepts as well. We analyze max-OEBP, where a packed bin is valid if by excluding its largest item, the total size of items is below 1. For this variant, we study the case of general item sizes, and the parametric case with bounded item sizes, which shows the effect of small items. Finally, we briefly discuss min-OEBP, where a bin is valid if the total size of its items excluding the smallest item is below 1, which is known to be an entirely different problem.
Full work available at URL: https://arxiv.org/abs/2105.05923
Recommendations
Cites Work
- A simple on-line bin-packing algorithm
- New lower bounds for certain classes of bin packing algorithms
- An improved lower bound for on-line bin packing algorithms
- Fast algorithms for bin packing
- On-line bin packing in linear time
- Batched bin packing
- Title not available (Why is that?)
- Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
- A note on an open-end bin packing problem
- Lower bounds for batched bin packing
- A new lower bound for classic online bin packing
- Batched bin packing revisited
- A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
- The Ordered Open-End Bin-Packing Problem
- A new and improved algorithm for online bin packing
- Asymptotic fully polynomial approximation schemes for variants of open-end bin packing
- The Parametric Behavior of the First-Fit Decreasing Bin Packing Algorithm
- Parameterized on-line open-end bin packing
- Hardness of lazy packing and covering
- On lazy bin covering and packing problems
- Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
- Lower bound for 3-batched bin packing
- More on batched bin packing
- More on ordered open end bin packing
- A note on a variant of the online open end bin packing problem
- On bin packing with clustering and bin packing with delays
- The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items
- Packing small vectors
Cited In (2)
This page was built for publication: Open-end bin packing: new and old analysis approaches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2172402)
