Fast Approximation Algorithms for Fractional Packing and Covering Problems
Serge A. PlotkinDavid B. ShmoysÉva TardosPublished in: FOCS (1991)
Keyphrases
- approximation algorithms
- vertex cover
- np hard
- approximation schemes
- randomized algorithms
- np hardness
- special case
- exact algorithms
- set cover
- network design problem
- np complete
- constant factor
- minimum cost
- mixed integer programming
- quadratic program
- optimization problems
- polynomial time approximation
- worst case
- lower bound