Lower bounds on the performance of online algorithms for relaxed packing problems

DOI10.1007/978-3-031-06678-8_8OpenAlexW4285270231MaRDI QIDQ2169944

Leah Epstein, Łukasz Jeż, János Balogh, György Dósa

Publication date: 30 August 2022

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

zbMATH Keywords

online algorithmscompetitive ratiobin packing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Scheduling appointments online: the power of deferred decision-making

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online knapsack revisited
• New lower bounds for certain classes of bin packing algorithms
• Fair versus unrestricted bin packing
• Bin packing can be solved within 1+epsilon in linear time
• Offline first-fit decreasing height scheduling of power loads
• Online bin packing with cardinality constraints resolved
• Improved lower bounds for the online bin packing problem with cardinality constraints
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Lower bounds for several online variants of bin packing
• A new lower bound for classic online bin packing
• Approximation Algorithms for Demand Strip Packing
• Peak Demand Minimization via Sliced Strip Packing.

This page was built for publication: Lower bounds on the performance of online algorithms for relaxed packing problems