TY - JOUR
T1 - VERIFIED APPROXIMATION ALGORITHMS
AU - Essmann, Robin
AU - Nipkow, Tobias
AU - Robillard, Simon
AU - Sulejmani, Ujkan
N1 - Publisher Copyright:
© VERIFIED APPROXIMATION ALGORITHMS.
PY - 2022
Y1 - 2022
N2 - We present the first formal verification of approximation algorithms for NPcomplete optimization problems: vertex cover, independent set, set cover, center selection, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case. All proofs are uniformly invariant based.
AB - We present the first formal verification of approximation algorithms for NPcomplete optimization problems: vertex cover, independent set, set cover, center selection, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case. All proofs are uniformly invariant based.
UR - http://www.scopus.com/inward/record.url?scp=85127209964&partnerID=8YFLogxK
U2 - 10.46298/LMCS-18(1:36)2022
DO - 10.46298/LMCS-18(1:36)2022
M3 - Article
AN - SCOPUS:85127209964
SN - 1860-5974
VL - 18
SP - 36:1-36:21
JO - Logical Methods in Computer Science
JF - Logical Methods in Computer Science
IS - 1
ER -