Near-linear approximation algorithms for geometric hitting sets.
Pankaj K. AgarwalEsther EzraMicha SharirPublished in: SCG (2009)
Keyphrases
- approximation algorithms
- constant factor approximation
- np hard
- vertex cover
- special case
- worst case
- facility location problem
- network design problem
- minimum cost
- set cover
- constant factor
- primal dual
- np hardness
- randomized algorithms
- open shop
- exact algorithms
- quadratic program
- approximation schemes
- undirected graph
- markov chain