Abstract
We present the first formal verification of approximation algorithms
for NP-complete optimization problems: vertex cover, set cover, independent set,
center selection, load balancing, and bin packing. The proofs correct incompletenesses
in existing proofs and improve the approximation ratio in one case.
License
History
- June 29, 2021
- added theory Center_Selection by Ujkan Sulejmani
- February 8, 2021
- added theory Approx_SC_Hoare (Set Cover) by Robin Eßmann