Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements.

Alina Ene Ali Vakilian

Published in: STOC (2014)

Keyphrases

approximation algorithms
network design problem
np hard
undirected graph
special case
worst case
disjoint paths
minimum cost
vertex cover
exact algorithms
approximation ratio
constant factor
upper bound
primal dual