Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks.
Baruch AwerbuchTom LeightonPublished in: STOC (1994)
Keyphrases
- approximation algorithms
- dynamic networks
- np hard
- special case
- network structure
- worst case
- vertex cover
- network topology
- approximation ratio
- dynamic behavior
- network analysis
- primal dual
- temporal evolution
- disjoint paths
- set cover
- machine learning
- constant factor approximation
- randomized algorithms
- real world networks
- training set
- search algorithm