Open-end bin packing: new and old analysis approaches

DOI10.1016/J.DAM.2022.07.003MaRDI QIDQ2172402zbMATH OpenOpenAlexFDO

Authors Leah Epstein

Publication date 15 September 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.05923

zbMATH Keywords

bin packingasymptotic approximation ratioprice of clustering

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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.

Recommendations

• scientific article; zbMATH DE number 1934389
• A note on an open-end bin packing problem
• On bin packing with clustering and bin packing with delays
• The Ordered Open-End Bin-Packing Problem
• Parameterized on-line open-end bin packing

Cites work

• scientific article; zbMATH DE number 6678949 (Why is no real title available?)
• A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
• A new and improved algorithm for online bin packing
• A new lower bound for classic online bin packing
• A note on a variant of the online open end bin packing problem
• A note on an open-end bin packing problem
• A simple on-line bin-packing algorithm
• An improved lower bound for on-line bin packing algorithms
• Asymptotic fully polynomial approximation schemes for variants of open-end bin packing
• Batched bin packing
• Batched bin packing revisited
• Fast algorithms for bin packing
• Hardness of lazy packing and covering
• Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
• Lower bound for 3-batched bin packing
• Lower bounds for batched bin packing
• More on batched bin packing
• More on ordered open end bin packing
• New lower bounds for certain classes of bin packing algorithms
• On bin packing with clustering and bin packing with delays
• On lazy bin covering and packing problems
• On-line bin packing in linear time
• Packing small vectors
• Parameterized on-line open-end bin packing
• The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items
• The Ordered Open-End Bin-Packing Problem
• The Parametric Behavior of the First-Fit Decreasing Bin Packing Algorithm
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)

Cited in

(2)

• Several methods of analysis for cardinality constrained bin packing
• On bin packing with clustering and bin packing with delays

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)