Approximation Algorithms and Hardness of the k-Route Cut Problem

Julia Chuzhoy Yury Makarychev Aravindan Vijayaraghavan Yuan Zhou

Published in: CoRR (2011)

Keyphrases

approximation algorithms
np hard
np hardness
worst case
special case
integrality gap
vertex cover
minimum cost
set cover

open shop
np complete
computational complexity
approximation ratio
facility location problem
exact algorithms
polynomial time approximation
shortest path
network design problem

lower bound
approximation schemes
integer programming
randomized algorithms
constant factor
optimal solution
constant factor approximation
primal dual

greedy algorithm
scheduling problem
undirected graph
travel time
phase transition
branch and bound algorithm
error bounds
linear program