Verified approximation algorithms

MaRDI QIDQ5094121zbMATH OpenFDO

Authors Robin Eßmann, Tobias Nipkow, Simon Robillard, Ujkan Sulejmani

Publication date 2 August 2022

Full work available at URL https://arxiv.org/abs/2104.13851, https://lmcs.episciences.org/9148

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• Verified Approximation Algorithms
• Logic Based Program Synthesis and Transformation
• New approximation algorithms for the vertex cover problem
• Fast approximate probabilistically checkable proofs
• Proof verification and the hardness of approximation problems

Cites work

• A linear approximation algorithm for bin packing with absolute approximation factor \(\frac {3}{2}\)
• Cardinality of relations and relational approximation algorithms
• Concrete semantics. With Isabelle/HOL
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• Isabelle/HOL. A proof assistant for higher-order logic
• Logic Based Program Synthesis and Transformation
• Towards formal foundations for game theory
• Verified Approximation Algorithms
• Verifying an incremental theory solver for linear arithmetic in Isabelle/HOL

Cited in

(6)

• On minimising the maximum expected verification time
• scientific article; zbMATH DE number 1303350 (Why is no real title available?)
• scientific article; zbMATH DE number 2080213 (Why is no real title available?)
• Verified Approximation Algorithms
• Trustworthy Graph Algorithms (Invited Talk)
• When are software verification results valid for approximate hardware?

This page was built for publication: Verified approximation algorithms

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