Fast Approximation Algorithms for Multicommodity Flow Problems.
Frank Thomson LeightonFillia MakedonSerge A. PlotkinClifford SteinÉva TardosSpyros TragoudasPublished in: J. Comput. Syst. Sci. (1995)
Keyphrases
- approximation algorithms
- multicommodity flow problems
- np hard
- multicommodity flow
- series parallel
- special case
- worst case
- precedence constraints
- undirected graph
- vertex cover
- minimum cost
- primal dual
- open shop
- disjoint paths
- constant factor
- randomized algorithms
- constant factor approximation
- set cover
- approximation guarantees
- combinatorial auctions
- routing problem
- branch and bound