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.
- June 29, 2021
- added theory Center_Selection by Ujkan Sulejmani
- February 8, 2021
- added theory Approx_SC_Hoare (Set Cover) by Robin Eßmann
- Eßmann, R., Nipkow, T., Robillard, S., & Sulejmani, U. (2022). Verified Approximation Algorithms. Logical Methods in Computer Science, Volume 18, Issue 1. https://doi.org/10.46298/lmcs-18(1:36)2022