An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow.
Chandra ChekuriSanjeev KhannaF. Bruce ShepherdPublished in: Theory Comput. (2006)
Keyphrases
- integrality gap
- disjoint paths
- approximation algorithms
- worst case
- lower bound
- linear programming relaxation
- np hard
- approximation ratio
- linear program
- primal dual
- arbitrarily close
- minimum cost
- special case
- approximation guarantees
- undirected graph
- linear programming
- greedy algorithm
- constant factor
- upper bound
- feasible solution
- np hardness
- valid inequalities
- branch and bound