Faster Approximation Algorithms for Generalized Flow.
Kevin D. WayneLisa FleischerPublished in: SODA (1999)
Keyphrases
- approximation algorithms
- np hard
- special case
- min cost
- worst case
- vertex cover
- facility location problem
- minimum cost
- constant factor
- approximation ratio
- set cover
- open shop
- precedence constraints
- exact algorithms
- randomized algorithms
- approximation schemes
- primal dual
- np hardness
- network design problem
- disjoint paths
- constant factor approximation
- approximation guarantees
- polynomial time approximation
- resource allocation