Several methods of analysis for cardinality constrained bin packing

DOI10.1016/j.tcs.2022.11.034OpenAlexW3186511479MaRDI QIDQ5970788

Leah Epstein

Publication date: 21 December 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.11.034

zbMATH Keywords

bin packingasymptotic approximation ratioprice of clustering

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• New lower bounds for certain classes of bin packing algorithms
• Bin packing can be solved within 1+epsilon in linear time
• An improved lower bound for on-line bin packing algorithms
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• The optimal absolute ratio for online bin packing
• Lower bound for 3-batched bin packing
• Batched bin packing
• More on batched bin packing
• Fast algorithms for bin packing
• Algorithms for on-line bin-packing problems with cardinality constraints
• Cardinality constrained bin-packing problems
• Lower bounds for batched bin packing
• Online bin packing with cardinality constraints resolved
• On bin packing with clustering and bin packing with delays
• Improved lower bounds for the online bin packing problem with cardinality constraints
• The tight absolute bound of First Fit in the parameterized case
• Batched bin packing revisited
• Bounds for online bin packing with cardinality constraints
• AFPTAS Results for Common Variants of Bin Packing: A New Method for Handling the Small Items
• A simple on-line bin-packing algorithm
• A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Approximation schemes for ordered vector packing problems
• Packing Small Vectors
• On-line bin packing in linear time
• Online Bin Packing with Cardinality Constraints
• Lower bounds for several online variants of bin packing
• A new lower bound for classic online bin packing

This page was built for publication: Several methods of analysis for cardinality constrained bin packing