Stream: Archive Mirror: Isabelle Users Mailing List

Topic: [isabelle] New in the AFP: Verified Approximation Algorithms

Email Gateway (Aug 22 2022 at 21:14):

From: Lawrence Paulson <lp15@cam.ac.uk>
Another day, another AFP entry. Eßmann, Nipkow and Robillard present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, load balancing, and bin packing. The proofs correct incompletenesses in existing proofs and improve the approximation ratio in one case.

You will find it online at

https://www.isa-afp.org/entries/Approximation_Algorithms.html

Keep them coming!

Larry Paulson

Last updated: May 06 2024 at 12:29 UTC