Formal Development and Verification of Approximation Algorithms Using Auxiliary Variables.

Rudolf Berghammer Markus Müller-Olm

Published in: LOPSTR (2003)

Keyphrases

approximation algorithms
auxiliary variables
np hard
special case
worst case
vertex cover
minimum cost
primal dual
set cover
randomized algorithms
approximation schemes
constant factor
image processing
multiscale
combinatorial auctions
image segmentation
graph cuts
linear programming
scheduling problem