Discovering and certifying lower bounds for the online bin stretching problem

DOI10.1016/J.TCS.2022.10.004OpenAlexW2997451510MaRDI QIDQ2089680FDOQ2089680

Authors: Martin Böhm, Bertrand Simon 

Publication date: 24 October 2022

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

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

Recommendations

• Improved lower bounds for the online bin stretching problem
• Online bin stretching with three bins
• On-line bin-stretching
• Better Algorithms for Online Bin Stretching
• A new lower bound for classic online bin packing

zbMATH Keywords

proof assistantcertifying algorithmsonline bin stretchingonline lower bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Isabelle/HOL. A proof assistant for higher-order logic
• Designing programs that check their work
• Certifying algorithms
• Semi on-line algorithms for the partition problem
• On-line bin-stretching
• Better Algorithms for Online Bin Stretching
• A framework for the verification of certifying computations
• Improved lower bounds for the online bin stretching problem
• Online bin stretching with three bins
• Trustworthy Graph Algorithms (Invited Talk)

Cited In (3)

• Online bin covering: expectations vs. guarantees
• Better Algorithms for Online Bin Stretching
• Online Bin Covering: Expectations vs. Guarantees

Uses Software

• Coq
• LEDA
• Isabelle/HOL
• OpenMPI
• binstretch

This page was built for publication: Discovering and certifying lower bounds for the online bin stretching problem

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