A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover.
Nikhil BansalAnupam GuptaRavishankar KrishnaswamyPublished in: SODA (2010)
Keyphrases
- set cover
- min sum
- np hard
- approximation algorithms
- greedy algorithm
- network flow
- lower bound
- constant factor
- constant factor approximation algorithm
- solution space
- convex hull
- greedy heuristic
- optimal solution
- knapsack problem
- integer programming
- minimum cost
- goal programming
- linear programming
- worst case
- min cut
- special case
- training data