Verified Approximation Algorithms.

Robin Eßmann Tobias Nipkow Simon Robillard

Published in: IJCAR (2) (2020)

Keyphrases

approximation algorithms
np hard
special case
worst case
vertex cover
minimum cost
facility location problem
set cover
primal dual
exact algorithms
network design problem
approximation ratio
open shop
randomized algorithms
undirected graph
constant factor
np hardness
approximation guarantees
approximation schemes