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

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

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

Publication date: 30 August 2022

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

zbMATH Keywords

online algorithmsbin packingcompetitive ratio

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Scheduling appointments online: the power of deferred decision-making
• Lower bounds on the performance of online algorithms for relaxed packing problems
• Title not available (Why is that?)
• Improved Lower Bound for Online Strip Packing

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

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