Approximation algorithms for constructing some required structures in digraphs.
Jianping LiYu GeShuai HeJunran LichenPublished in: Eur. J. Oper. Res. (2014)
Keyphrases
- approximation algorithms
- np hard
- undirected graph
- special case
- worst case
- primal dual
- minimum cost
- approximation ratio
- vertex cover
- precedence constraints
- facility location problem
- network design problem
- np hardness
- constant factor approximation
- constant factor
- set cover
- equivalence classes
- combinatorial auctions
- randomized algorithms
- directed graph
- open shop