Discovering and certifying lower bounds for the online bin stretching problem

DOI10.1016/J.TCS.2022.10.004MaRDI QIDQ2089680zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

certifying algorithmsonline bin stretchingonline lower boundproof assistant

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cites work

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

Cited in

(4)

• Online Bin Covering: Expectations vs. Guarantees
• Online bin covering: expectations vs. guarantees
• Better Algorithms for Online Bin Stretching
• Improved online load balancing with known makespan

Describes a project that uses

Uses Software

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

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)