Abstract: |
We present the first formal verification of approximation algorithms
-for NP-complete optimization problems: vertex cover, independent set,
+for NP-complete optimization problems: vertex cover, set cover, independent set,
load balancing, and bin packing. The proofs correct incompletenesses
-in existing proofs and improve the approximation ratio in one case. |
+in existing proofs and improve the approximation ratio in one case.
+A detailed description of our work has been published in the proceedings of
+IJCAR 2020.
BibTeX: |
@article{Approximation_Algorithms-AFP,
author = {Robin Eßmann and Tobias Nipkow and Simon Robillard},
title = {Verified Approximation Algorithms},
journal = {Archive of Formal Proofs},
month = jan,
year = 2020,
note = {\url{https://isa-afp.org/entries/Approximation_Algorithms.html},
Formal proof development},
ISSN = {2150-914x},
}
|