Approximation Algorithms for Survivable Multicommodity Flow Problems with Applications to Network Design.
Ajay Kumar TodimalaByrav RamamurthyPublished in: INFOCOM (2006)
Keyphrases
- multicommodity flow problems
- network design problem
- approximation algorithms
- network design
- series parallel
- np hard
- communication networks
- special case
- multicommodity flow
- worst case
- minimum cost
- precedence constraints
- vertex cover
- undirected graph
- network architecture
- primal dual
- facility location
- constant factor
- branch and bound
- upper bound
- linear program
- scheduling problem