Verified Approximation Algorithms

DOI10.1007/978-3-030-51054-1_17MaRDI QIDQ5049009zbMATH OpenOpenAlexFDO

Authors Robin Eßmann, Tobias Nipkow, Simon Robillard

Publication date 9 November 2022

Published in Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-51054-1_17

Mathematics Subject Classification ID

Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Recommendations

• Verified approximation algorithms
• Approximate verification and enumeration problems
• scientific article; zbMATH DE number 1256636
• scientific article; zbMATH DE number 4088841
• Probabilistically checkable proofs and their consequences for approximation algorithms
• Lectures on proof verification and approximation algorithms
• scientific article; zbMATH DE number 1264429
• scientific article; zbMATH DE number 1330032
• Approximation algorithms

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
• Logic Based Program Synthesis and Transformation
• Verifying an incremental theory solver for linear arithmetic in Isabelle/HOL

Cited in

(4)

• scientific article; zbMATH DE number 1303350 (Why is no real title available?)
• scientific article; zbMATH DE number 2080213 (Why is no real title available?)
• On minimising the maximum expected verification time
• scientific article; zbMATH DE number 7566049 (Why is no real title available?)

Describes a project that uses

Uses Software

• Archive Formal Proofs

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 Q5049009)