Robin Eßmann ; Tobias Nipkow ; Simon Robillard ; Ujkan Sulejmani - Verified Approximation Algorithms

lmcs:7416 - Logical Methods in Computer Science, March 1, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:36)2022
Verified Approximation AlgorithmsArticle

Authors: Robin Eßmann ; Tobias Nipkow ; Simon Robillard ; Ujkan Sulejmani

We present the first formal verification of approximation algorithms for NP-complete 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.

https://doi.org/10.46298/lmcs-18(1:36)2022
Source: arXiv.org:2104.13851
Volume: Volume 18, Issue 1
Secondary volumes: Selected Papers of the 10th International Joint Conference on Automated Reasoning (IJCAR 2020)
Published on: March 1, 2022
Accepted on: October 7, 2021
Submitted on: April 29, 2021
Keywords: Computer Science - Logic in Computer Science, Computer Science - Data Structures and Algorithms
Licence: Attribution 4.0 International (CC BY 4.0)

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 2487 times.
This article's PDF has been downloaded 1113 times.