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

online algorithmsbin packingapproximation scheme

Mathematics Subject Classification ID

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

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 Ordered Open-End Bin-Packing Problem
• The optimal absolute ratio for online bin packing
• Two-bounded-space bin packing revisited

Cited in

(10)

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

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)