Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs.

Michel X. Goemans David P. Williamson

Published in: Comb. (1998)

Keyphrases

approximation algorithms
vertex cover
primal dual
np hard
planar graphs
special case
worst case
linear programming
minimum cost
undirected graph
convex optimization
constant factor
linear program
approximation ratio
polynomial time approximation
lower bound
convergence rate
integrality gap