Improved approximation algorithms for low-density instances of the Minimum Entropy Set Cover Problem.
Cosmin BonchisGabriel IstratePublished in: Inf. Process. Lett. (2014)
Keyphrases
- set cover
- approximation algorithms
- low density
- np hard
- greedy heuristics
- high density
- special case
- minimum cost
- greedy algorithm
- worst case
- exact algorithms
- vertex cover
- approximation ratio
- primal dual
- closest string
- network flow
- open shop
- randomized algorithms
- constant factor
- lower bound
- linear programming
- disjoint paths
- approximation guarantees
- constraint satisfaction
- search space