Verified Approximation Algorithms

04/28/2021
by   Robin Eßmann, et al.
0

We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, set cover, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset