Verified Approximation Algorithms

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

Simon Robillard, Robin Eßmann, Tobias Nipkow

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)

Related Items (1)

Unnamed Item

Uses Software

• Archive Formal Proofs

Cites Work

• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• A linear approximation algorithm for bin packing with absolute approximation factor \(\frac {3}{2}\)
• Verifying an incremental theory solver for linear arithmetic in Isabelle/HOL
• Concrete Semantics
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• Logic Based Program Synthesis and Transformation
• Cardinality of relations and relational approximation algorithms

This page was built for publication: Verified Approximation Algorithms