Hardness of Approximation for Vertex-Connectivity Network-Design Problems.

Guy Kortsarz Robert Krauthgamer James R. Lee

Published in: APPROX (2002)

Keyphrases

approximation algorithms
network design problem
np hard
worst case
network design
special case
network flow problem
branch and bound
phase transition
mixed integer programming
minimal cost
np complete
transportation networks
minimum cost
valid inequalities