Fast Approximation Algorithms for Multicommodity Flow Problems
Frank Thomson LeightonFillia MakedonSerge A. PlotkinClifford SteinÉva TardosSpyros TragoudasPublished in: STOC (1991)
Keyphrases
- approximation algorithms
- multicommodity flow problems
- np hard
- multicommodity flow
- series parallel
- special case
- worst case
- undirected graph
- precedence constraints
- approximation ratio
- minimum cost
- primal dual
- vertex cover
- randomized algorithms
- set cover
- open shop
- disjoint paths
- constant factor
- approximation guarantees
- computational complexity
- search space