PTAS for Weighted Set Cover on Unit Squares.
Thomas ErlebachErik Jan van LeeuwenPublished in: APPROX-RANDOM (2010)
Keyphrases
- set cover
- approximation algorithms
- np hard
- greedy heuristics
- greedy algorithm
- special case
- approximation schemes
- minimum cost
- polynomial time approximation
- worst case
- network flow
- greedy heuristic
- hough transform
- primal dual
- solution space
- data sets
- constraint satisfaction problems
- lower bound
- search algorithm
- optimal solution