Better Inapproximability Bounds and Approximation Algorithms for Min-Max Tree/Cycle/Path Cover Problems.
Wei YuZhaohui LiuPublished in: COCOON (2017)
Keyphrases
- approximation algorithms
- min max
- vertex cover
- randomized algorithms
- worst case
- minimum cost
- exact algorithms
- approximation schemes
- np hard
- special case
- network design problem
- np hardness
- facility location problem
- quadratic program
- primal dual
- upper bound
- lower bound
- approximation ratio
- set cover
- np complete
- max min
- open shop
- learning algorithm
- constant factor approximation
- approximation guarantees
- precedence constraints
- combinatorial auctions
- optimization problems