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
    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)

    Share and export

    Consultation statistics

    This page has been seen 1334 times.
    This article's PDF has been downloaded 681 times.