More on ordered open end bin packing

DOI10.1007/S10951-021-00709-3MaRDI QIDQ2066681zbMATH OpenOpenAlexFDO

Authors János Balogh, Leah Epstein, Asaf Levin

Publication date 14 January 2022

Published in Journal of Scheduling (Search for Journal in Brave)

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

zbMATH Keywords

approximation schemebin packingonline algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We consider the Ordered Open End Bin Packing problem. Items of sizes in $(0,1]$ are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin for which the current total size strictly below $1$. This means also that the bin can be overloaded by its last packed item. We improve lower and upper bounds on the asymptotic competitive ratio in the online case. Specifically, we design the first algorithm whose asymptotic competitive ratio is strictly below $2$ and it is close to the lower bound. This is in contrast to the best possible absolute approximation ratio, which is equal to $2$. We also study the offline problem where the sequence of items is known in advance, while items are still assigned to bins based on their order in the sequence. For this scenario we design an asymptotic polynomial time approximation scheme.

Recommendations

• The Ordered Open-End Bin-Packing Problem
• A note on an open-end bin packing problem
• scientific article; zbMATH DE number 1934389
• An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem
• scientific article; zbMATH DE number 1934401

Cites work

• A lower bound for online rectangle 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
• Bin packing can be solved within 1+epsilon in linear time
• Bin packing with ``largest in bottom constraint: tighter bounds and generalizations
• Bounds for online bin packing with cardinality constraints
• Colored bin packing: online algorithms and lower bounds
• Fully dynamic bin packing revisited
• Hardness of lazy packing and covering
• Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
• Integer Programming with a Fixed Number of Variables
• New lower bounds for certain classes of bin packing algorithms
• Offline black and white bin packing
• On lazy bin covering and packing problems
• On online bin packing with LIB constraints
• On-line bin packing in linear time
• Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing
• Online results for black and white bin packing
• Parameterized on-line open-end bin packing
• The optimal absolute ratio for online bin packing
• The Ordered Open-End Bin-Packing Problem
• Two-bounded-space bin packing revisited

Cited in

(14)

• Parameterized on-line open-end bin packing
• More on batched bin packing
• Comparing the costs of any fit algorithms for bin packing
• Open-end bin packing: new and old analysis approaches
• A note on a variant of the online open end bin packing problem
• An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem
• The Ordered Open-End Bin-Packing Problem
• scientific article; zbMATH DE number 1934401 (Why is no real title available?)
• A note on an open-end bin packing problem
• Tighter bounds for the harmonic bin packing algorithm
• Bin packing with thresholds: mathematical models and theoretical results
• On open-end bin packing games
• Generalized last open-end bin packing problem
• Asymptotic fully polynomial approximation schemes for variants of open-end bin packing

This page was built for publication: More on ordered open end bin packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2066681)