Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
Venkatesan GuruswamiSanjeev KhannaRajmohan RajaramanF. Bruce ShepherdMihalis YannakakisPublished in: STOC (1999)
Keyphrases
- disjoint paths
- related problems
- approximation algorithms
- np hard
- np hardness
- worst case
- special case
- minimum cost
- set cover
- vertex cover
- network design problem
- open shop
- approximation ratio
- undirected graph
- primal dual
- facility location problem
- np complete
- computational complexity
- precedence constraints
- approximation schemes
- knapsack problem
- randomized algorithms
- lower bound
- optimal solution
- integer programming