Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
Allan BorodinRafail OstrovskyYuval RabaniPublished in: Mach. Learn. (2004)
Keyphrases
- approximation algorithms
- vertex cover
- np hard
- np hardness
- approximation schemes
- special case
- worst case
- randomized algorithms
- np complete
- network design problem
- minimum cost
- exact algorithms
- approximation ratio
- facility location problem
- constant factor
- clustering algorithm
- learning algorithm
- search algorithm
- optimization problems
- data points
- lower bound