Verified Approximation Algorithms

DOI10.1007/978-3-030-51054-1_17OpenAlexW3013252759MaRDI QIDQ5049009FDOQ5049009

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On minimising the maximum expected verification time
• Title not available (Why is that?)

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)