Discovering and certifying lower bounds for the online bin stretching problem

DOI10.1016/j.tcs.2022.10.004OpenAlexW2997451510MaRDI QIDQ2089680

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

zbMATH Keywords

proof assistantcertifying algorithmsonline bin stretchingonline lower bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

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

Cites Work

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

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